We define \(3\)-PBIBDs to simplify the notation used in one of Hanani’s celebrated papers, where he developed important tools for the constructions of \(3\)-designs. A special case of the \(3\)-PBIBD, a \(3\)-GDD\((n,2,4;\lambda_1,\lambda_2)\), was recently studied in [5] and [6]. In this note, we develop necessary conditions for the existence of another special case, denoted \(3'\)-GDD\((n,3,4;\) \(\mu_1,\mu_2)\), and provide several constructions for infinite families of these designs. We show that the necessary conditions are sufficient for the existence of \(3'\)-GDD\((n,3,4;\mu_1,\mu_2)\) when \(\mu_2=0\) and \(\mu_1\) is arbitrary. In particular, when \(\mu_1\) is even and \(\mu_2 = 0\), such designs exist for all \(n\); and when \(\mu_1\) is odd and \(\mu_2 = 0\), they exist for even \(n\). We also provide instances of nonexistence.

A Kempe chain in a colored graph is a maximal connected component containing at most two colors. Kempe chains have played an important role historically in the study of the Four Color Problem. Some methods of systematically applying Kempe chain color exchanges have been studied by Alfred Errera and Weiguo Xie. A map constructed by Errera represents an important counterexample to some implementations of these methods. Using the ideas of Irving Kittell, we determine all colorings of the Errera map which form such a counterexample and describe how to color them individually. We then extend our results from the Errera map to a family of graphs containing the Errera map in a specific way. Being able to color this family of graphs appears to address many cases which prove difficult for the previous systematic color exchange methods.

We use Rosa-type labelings to decompose complete graphs into unicyclic, disconnected, non-bipartite graphs on nine edges. For any such graph \(H\), we prove there exists an \(H\)-design of \(K_{18k+1}\) and \(K_{18k}\) for all positive integers \(k.\)

In this paper, we continue investigation of decompositions of complete graphs into graphs with seven edges. The spectrum has been completely determined for such graphs with at most six vertices. The spectrum for bipartite graphs is completely known for graphs with seven or eight vertices. In this paper we completely solve the case of disconnected unicyclic bipartite graphs with seven edges by studying the remaining graphs with nine or ten vertices.

Let \(G\) be a disconnected tripartite unicyclic graph on seven edges with two or more connected components. We prove that \(G\) decomposes the complete graph \(K_{n}\) whenever \(n\equiv0,1\pmod{14}\) using labeling techniques.

Let \(G\) be a graph. We introduce the balanced antimagic labeling as an analogue to the antimagic labeling. A \(k\)-total balanced antimagic labelling is a map \(c\colon V (G)\cup E(G) \to \{1,2,\ldots,k\}\) such that: the label classes differ in size by at most one, each vertex \(x\) is assigned the weight \(w(x)={c}(x)+\sum\limits_{x\in e}{c}(e)\), and \(w(x)\neq w(y)\) for \(x\neq y\).

We present several properties of balanced antimagic labeling. We also derive such a labeling for complete graphs and complete bipartite graphs.

For a subgraph \(G\) of the complete graph \(K_n\), a \(G\)-design of order \(n\) is a partition of the edges of \(K_n\) into edge-disjoint copies of \(G.\) For a given graph \(G\), the \(G\)-design spectrum problem asks for which \(n\) a \(G\)-design of order \(n\) exists. This problem has recently been completely solved for every graph \(G\) with less than seven edges, with the lone exception of \(G \cong K_3 \cup 2K_2,\) the disconnected graph consisting of a triangle and two isolated edges. In this article, we solve this problem by proving that a \(K_3 \cup 2K_2\)-design of order \(n\) exists if and only if \(n \equiv 0 \; \textrm{or} \; 1 \pmod{5}\) and \(n\geq 10.\)

A question involving a chess piece called a prince on the \(8\times 8\) chessboard leads to a concept in graph theory involving total domination in the Cartesian products of paths and cycles. A vertex \(u\) in a graph \(G\) totally dominates a vertex \(v\) if \(v\) is adjacent to \(u\). A subset \(S\) of the vertex set of a graph \(G\) is a total dominating set for \(G\) if every vertex of \(G\) is totally dominated by at least one vertex of \(S\). If \(S\) is a total dominating set of a graph \(G\), then \(S(v)\) denotes the number of vertices in \(S\) that totally dominate \(v\). A total dominating set \(S\) in a graph \(G\) is called a proper total dominating set if \(S(u) \ne S(v)\) for every two adjacent vertices \(u\) and \(v\) of \(G\). It is shown that \(C_n \ \Box \ K_2\) possesses a proper total dominating set if and only if \(n\ge 4\) is even and the graph \(C_n \ \Box \ P_m\) possesses a proper total dominating set for every even integer \(n \ge 4\) and every integer \(m \ge 3\). Furthermore, \(C_3 \ \Box \ P_m\) possesses a proper total dominating set if and only if \(m = 3\). If \(n\ge 5\) is an odd integer and \(m\equiv 3 \pmod 4\), then \(C_n \ \Box \ P_m\) has a proper total dominating set. If at least one of \(n\) and \(m\) is even, then \(C_n \ \Box \ C_m\) has a proper total dominating set. The graphs \(C_n \ \Box \ C_m\) are further studied when both \(n\) and \(m\) are odd. Other results and questions are also presented.

For a graph \(F\) and a positive integer \(t\), the vertex-disjoint Ramsey number \(VR_t(F)\) is the minimum positive integer \(n\) such that every red-blue coloring of the edges of the complete graph \(K_n\) of order \(n\) results in \(t\) pairwise vertex-disjoint monochromatic copies of subgraphs isomorphic to \(F\), while the edge-disjoint Ramsey number \(ER_t(F)\) is the corresponding number for edge-disjoint subgraphs. These numbers have been investigated for the three connected graphs \(K_3\), \(P_4\) and \(K_{1, 3}\) of size 3. For two vertex-disjoint graphs \(G\) and \(H\), let \(G+H\) denote the union of \(G\) and \(H\). Here we study these numbers for the two disconnected graphs \(3K_2\) and \(P_3+P_2\) of size 3. It is shown that \(VR_t(3K_2)= 6t+2\) and \(VR_t(P_3+P_2)= 5t+1\) for every positive integer \(t\). The numbers \(ER_t(3K_2)\) and \(ER_t(P_3+P_2)\) are determined for \(t \le 4\) and bounds are established for \(ER_t(3K_2)\) and \(ER_t(P_3+P_2)\) when \(t \ge 5\). Other results and problems are presented as well.

Every red-blue coloring of the edges of a graph \(G\) results in a sequence \(G_1\), \(G_2\), \(\ldots\), \(G_{\ell}\) of pairwise edge-disjoint monochromatic subgraphs \(G_i\) (\(1 \le i \le \ell\)) of size \(i\) such that \(G_i\) is isomorphic to a subgraph of \(G_{i+1}\) for \(1 \le i \le \ell-1\). Such a sequence is called a Ramsey chain in \(G\) and \(AR_c(G)\) is the maximum length of a Ramsey chain in \(G\) with respect to a red-blue coloring \(c\). The Ramsey index \(AR(G)\) of \(G\) is the minimum value of \(AR_c(G)\) among all red-blue colorings \(c\) of \(G\). Several results giving the Ramsey indexes of graphs are surveyed. A galaxy is a graph each of whose components is a star. Results and conjectures on Ramsey indexes of galaxies are presented.