We show that every hamiltonian claw-free graph with a vertex \(x\) of degree \(d(x) \geq 7\) has a \(2\)-factor consisting of exactly two cycles.

This paper presents two new algorithms for generating \((n,2)\) de Bruijn sequences which possess certain properties. The sequences generated by the proposed algorithms may be useful for experimenters to systematically investigate intertrial repetition effects. Characteristics are compared with those of randomly sampled \((n,2)\) de Bruijn sequences.

Let \(\alpha(G)\) and \(\tau(G)\) denote the independence number and matching number of a graph \(G\), respectively. The tensor product of graphs \(G\) and \(H\) is denoted by \(G \times H\). Let \(\underline{\alpha}(G \times H) = \max \{\alpha(G) \cdot n(H), \alpha(H) \cdot n(G)\}\) and \(\underline{\tau}(G \times H) = 2\tau(G) \cdot \tau(H)\), where \(\nu(G)\) denotes the number of vertices of \(G\). It is easy to see that \(\alpha(G \times H) \geq \underline{\alpha}(G \times H)\) and \(\beta(G \times H) \geq \underline{\tau}(G \times H)\). Several sufficient conditions for \(\alpha(G \times H) > \underline{\alpha}(G \times H)\) are established. Further, a characterization is established for \(\alpha(G \times H) = \underline{\tau}(G \times H)\). We have also obtained a necessary condition for \(\alpha(G \times H) = \underline{\alpha}(G \times H)\). Moreover, it is shown that neither the hamiltonicity of both \(G\) and \(H\) nor large connectivity of both \(G\) and \(H\) can guarantee the equality of \(\alpha(G \times H)\) and \(\underline{\alpha}(G \times H)\).

A graphoidal cover of a graph \(G\) is a collection \(\psi\) of (not necessarily open) paths in \(G\) such that every vertex of \(G\) is an internal vertex of at most one path in \(\psi\) and every edge of \(G\) is an exactly one path in \(\psi\). If further no member of \(\psi\) is a cycle, then \(\psi\) is called an acyclic graphoidal cover of \(G\). The minimum cardinality of an acyclic graphoidal cover is called the acyclic graphoidal covering number of \(G\) and is denoted by \(\eta_a\). In this paper, we characterize the class of graphs for which \(\eta_a = q – p\), where \(p\) and \(q\) denote respectively the order and size of \(G\).

The dissociation number of a graph \(G\) is the number of vertices in a maximum size induced subgraph of \(G\) with vertex degrees at most \(1\). The problem of finding the dissociation number was introduced by Yannakakis, who proved it is NP-hard on the class of bipartite graphs. In this paper, we analyze the dissociation number problem restricted to the class of bipartite graphs in more detail. We strengthen the result of Yannakakis by reducing the problem, in polynomial time, from general bipartite graphs to some particular classes, such as bipartite graphs with maximum degree \(3\) or \(C_4\)-free bipartite graphs. Besides the negative results, we prove that finding the dissociation number is polynomially solvable for bipartite graphs containing no induced subgraph isomorphic to a tree with exactly three vertices of degree \(1\) of distances \(1\), \(2\), and \(3\) from the only vertex of degree \(3\).

The induced matching number of a graph \(G\) is the number of edges in a maximum size induced subgraph of \(G\) with vertex degrees equal to \(1\). Analogous results hold for the induced matching number.

A vertex \(k\)-coloring of a graph \(G\) is acyclic if no cycle is bichromatic. The minimum integer \(k\) such that \(G\) admits an acyclic \(k\)-coloring is called the acyclic chromatic number of \(G\), denoted by \(\chi_a(G)\). In this paper, we discuss some properties of maximal acyclic \(k\)-colorable graphs, prove a sharp lower bound of the \(\chi_a(G)\) and get some results about the relation between \(\chi(G)\) and \(\chi_a(G)\). Furthermore, a conjecture of B. Grünbaum that \(\chi_a(G) \leq \Delta+1\) is proved for maximal acyclic \(k\)-colorable graphs.

In this paper, we focus on the existence of \(2\)-critical sets in the latin square corresponding to the elementary abelian \(2\)-group of order \(2^n\). It has been shown by Stinson and van Rees that this latin square contains a \(2\)-critical set of volume \(4^n – 3^n\). We provide constructions for \(2\)-critical sets containing \(4^n – 3^n + 1 – \left(2^{k-1} + 2^{m-1} + 2^{n-(k+m+1)}\right)\) entries, where \(1 \leq k \leq n\) and \(1 \leq m \leq n – k\). That is, we construct \(2\)-critical sets for certain values less than \(4^n – 3^n + 1 – 3\cdot 2^{\lfloor n/3\rfloor – 1}\). The results raise the interesting question of whether, for the given latin square, it is possible to construct \(2\)-critical sets of volume \(m\), where \(4^n – 3^n + 1 – 3\cdot 2^{\lfloor n/3\rfloor – 1} < m < 4^n – 3^n\).

In this paper, we find explicit formulas, or recurrences, in terms of generating functions for the cardinalities of the sets \(S_{n}(T; \tau)\) of all permutations in \(S_n\) that contain \(\tau \in S_k\) exactly once and avoid a subset \(T \subseteq S_3\) where \(|T| \geq 2\).

A digraph \(T\) is called strongly connected if for every pair of vertices \(u\) and \(v\) there exists a directed path from \(u\) to \(v\) and a directed path from \(v\) to \(u\). Denote the in-degree and out-degree of a vertex \(v\) of \(T\) by \(d^-(v)\) and \(d^+(v)\), respectively. We define \(\delta^- = \min_{v\in V(T)} \{d^-(v)\}\), and \(\delta_+ = \min_{v\in V(T)} \{d^+(v)\}\). Let \(T_0\) be a \(7\)-tournament which contains no transitive \(4\)-subtournament. Let \(T\) be a strong tournament, \(T \ncong T_0\) and \(k \geq 2\). In this paper, we show that if \(\delta^+ + \delta^- \geq \frac{k-2}{k-1}n+3k(k-1)\), then \(T\) can be partitioned into \(k\) cycles. When \(n \geq 3k(k-1)\) a regular strong \(n\)-tournament can be partitioned into \(k\) cycles and a almost regular strong \(n\)-tournament can be partitioned into \(k\) cycles when \(n \geq (3k+1)(k-1)\). Finally, if a strong tournament \(T\) can be partitioned into \(k\) cycles, \(q\) is an arbitrary positive integer not larger than \(k\). We prove that \(T\) can be partitioned into \(q\) cycles.

Let \(G = (V, E)\) be a simple graph. Let \(\alpha\) and \(\mathrm{IR}\) be the independence number and upper irredundance number of \(G\), respectively. In this paper, we prove that for any graph \(G\) of order \(n\) with maximum degree \(\Delta \geq 1\), \(\mathrm{IR}(G) – \alpha(G) \leq \frac{\Delta -2}{2\Delta }n\). When \(\Delta = 3\), the result was conjectured by Rautenbach.