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.

We first establish the relationship between the largest eigenvalue of the Laplacian matrix of a graph and its bipartite density. Then, we present lower and upper bounds for the largest Laplacian eigenvalue of a graph in terms of its largest degree and diameter.

In this paper, we prove the gracefulness of the class of graphs denoted by \(\mathcal{P}_{a,b}\).

Let \(D\) be a dominating set of a simple graph \(G = (V, E)\). If the subgraph \((V – D)_G\)induced by the set \(V – D\) is disconnected, then \(D\) is called a split dominating set of \(G\), and if \(\langle D\rangle_G\) has no edges, then \(D\) is an independent dominating set of \(G\). If every vertex in \(V\) is adjacent to some vertex of \(D\) in \(G\), then \(D\) is a total dominating set of \(G\). The split domination number \(\gamma_s(G)\), independent domination number \(i(G)\), and total domination number \(\gamma_t(G)\) equal the minimum cardinalities of a split, independent, and total dominating set of \(G\), respectively. The concept of split domination was first defined by Kulli and Janakiram in 1997 [4], while total domination was introduced by Cockayne, Dawes, and Hedetniemi in 1980 [2].

In this paper, we study the split, independent, and total domination numbers of corona \(G \circ H\) and generalized coronas \(kG \circ H\) of graphs.