A graph \(G\) is 2-stratified if its vertex set is partitioned into two classes (each of which is a stratum or a color class), where the vertices in one class are colored red and those in the other class are colored blue. Let \(F\) be a 2-stratified graph rooted at some blue vertex \(v\). An \(F\)-coloring of a graph is a red-blue coloring of the vertices of \(G\) in which every blue vertex \(v\) belongs to a copy of \(F\) rooted at \(v\). The \(F\)-domination number \(\gamma_F(G)\) is the minimum number of red vertices in an \(F\)-coloring of \(G\). In this paper, we determine the \(F\)-domination number of the prisms \(C_n \times K_2\) for all 2-stratified claws \(F\) rooted at a blue vertex.

In this study, we consider the effect on the upper irredundance number \(IR(G)\) of a graph \(G\) when an edge is added joining a pair of non-adjacent vertices of \(G\). We say that \(G\) is \(IR\)-insensitive if \(IR(G + e) = IR(G)\) for every edge \(e \in \overline{E}\). We characterize \(IR\)-insensitive bipartite graphs and give a constructive characterization of graphs \(G\) for which the addition of any edge decreases \(IR(G)\). We also demonstrate the existence of a wide class of graphs \(G\) containing a pair of non-adjacent vertices \(u,v\) such that \(IR(G + uv) > IR(G)\).

A graph \(G\) is called \((a:b)\)-choosable if for every assignment of \(a\)-sets \(L(v)\) to the vertices of \(G\) it is possible to choose \(b\)-subsets \(M(v) \subseteq L(v)\) so that adjacent vertices get disjoint subsets. We give a different proof of a theorem of Tuza and Voigt that every \(2\)-choosable graph is \((2k:k)\)-choosable for any positive integer \(k\). Our proof is algorithmic and can be implemented to run in time \(O(k|V(G)|)\).

We prove some general results on irredundant sets of queens on chessboards, and determine the irredundance numbers of the queens graph \(Q_n\), for \(n = 5, 6\).

Let \(G\) be a graph. The weak domination number of \(G\), \(\gamma_w(G)\), is the minimum cardinality of a set \(D\) of vertices where every vertex \(u \notin D\) is adjacent to a vertex \(v \in D\), where \(\deg(v) \leq \deg(u)\). The strong domination number of \(G\), \(\gamma_s(G)\), is the minimum cardinality of a set  \(D\) of vertices where every vertex \(u \notin D\) is adjacent to a vertex \(v \in D\), where \(\deg(v) \geq \deg(u)\). Similarly, the independent weak domination number, \(i_w(G)\), and the independent strong domination number, \(i_{st}(G)\), are defined with the additional requirement that the set \(D\) is independent. We find upper bounds on the number of edges of a graph in terms of the number of vertices and for each of these four domination parameters. We also characterize all graphs where equality is achieved in each of the four bounds.

For \(k \geq 2\), the \(P_k\)-free domination number \(\gamma(G; -P_k)\) is the minimum cardinality of a dominating set \(S\) in \(G\) such that the subgraph \(\langle S \rangle\) induced by \(S\) contains no path \(P_k\) on \(k\) vertices. The path-free domination number is at least the domination number and at most the independent domination number of the graph. We show that if \(G\) is a connected graph of order \(n \geq 2\), then \(\gamma(G; -P_k) \leq n + 2(k – 1) – 2\sqrt{n(k-1)}\), and this bound is sharp. We also give another bound on \(\gamma(G; -P_k)\) that yields the corollary: if \(G\) is a graph with \(\gamma(G) \geq 2\) that is \(K_{1,t+1}\)-free and \((K_{1,t+1}+e)\)-free (\(t \geq 3\)), then \(\gamma(G; -P_3) \leq (t-2)\gamma(G) – 2(t-3)\), and we characterize the extremal graphs for the corollary’s bound. Every graph \(G\) with maximum degree at most \(3\) is shown to have equal domination number and \(P_3\)-free domination number. We define a graph \(G\) to be \(P_k\)-domination perfect if \(\gamma(H) = \gamma(H; -P_k)\) for every induced subgraph \(H\) of \(G\). We show that a graph \(G\) is \(P_3\)-domination perfect if and only if \(\gamma(H) = \gamma(H; -P_3)\) for every induced subgraph \(H\) of \(G\) with \(\gamma(H) = 3\).

In this paper, we show that group divisible designs with block size five, group-type and index odd exist with a few possible exceptions.

A digraph \(D\) is called semicomplete \(c\)-partite if its vertex set \(V(D)\) can be partitioned into \(c\) sets (partite sets) such that for any two vertices \(x\) and \(y\) in different partite sets, at least one arc between \(x\) and \(y\) is in \(D\) and there are no arcs between vertices in the same partite set. The path covering number of \(D\) is the minimum number of paths in \(D\) that are pairwise vertex disjoint and cover the vertices of \(D\). Volkmann (1996) has proved two sufficient conditions on hamiltonian paths in semicomplete multipartite digraphs and conjectured two related sufficient conditions. In this paper, we derive sufficient conditions for a semicomplete multipartite digraph to have path covering number at most \(k\) and show that Volkmann’s results and conjectures can be readily obtained from our conditions.

The Fibonacci number of a graph is the number of independent sets of the graph. In this paper, we compute algorithmically the Fibonacci numbers of lattice product graphs.

In this note, we solve a conjecture of Dénes, Mullen, and Suchower [2] on power sets of Latin squares.