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\).