In this section we consider 4-regular graphs and obtain a characterization of perfect 2-colorings of toroidal grids. The ten possible 2-coloring matrices for 4-regular graphs are listed below.
A2,4=[3113]A3,3=[2222], A3,4=[2213]A4,2=[1331], A4,3=[1322], A4,4=[1313]A5,1=[0440], A5,2=[0431], A5,3=[0422], A5,4=[0413]
Definition 3.1
Suppose G1(V1, E1) and G2(V2, E2) are simple graphs. The Cartesian product of G1 and G2, written G1□G2, is the graph with vertex set V1 × V2 in which (u, v) is adjacent to (u′, v′) if and only if u = u′ and vv′ ∈ E2, or v = v′ and uu′ ∈ E1. Note that the Cartesian product operation is symmetric; that is G1□G2 ≅ G2□G1.
Let n, m ≥ 3 be integers. The Cartesian product of two cycles, G = Cn□Cm, is known as a toroidal grid graph (See Figure 1). According to the definition, the toroidal grid is a 4-regular graph.
Suppose V(G) = {(i, j)| 0 ≤ i ≤ n − 1; 0 ≤ j ≤ m − 1}. To show perfect 2-colorings of G in the next theorems, we consider a part of G as an orthogonal grid, as shown in Figure 2. We assume that its horizontal paths are of length n such that the leftmost vertex of each path is adjacent to rightmost vertex of it, and its vertical paths are of length m such that the topmost vertex of each path is adjacent to the bottom-most vertex of it. Assume that the vertex in the box is (0, 0). Index i increases with left-right orientation of the horizontal cycles, and index j increases with down-up orientation of the vertical cycles.
In the following, we investigate necessary and sufficient conditions for the admissibility of each of ten coloring matrices for this class of graphs. Note that since Cn□Cm ≅ Cm□Cn, in the following results, we can switch conditions from m to n and vice versa.
Theorem 3.2
Let 3 ≤ n, m < ∞. The toroidal grid G = Cn□Cm admits a perfect 2-coloring with matrix A2,4if and only if m ≡ 0 (mod 4).
Proof
Suppose a perfect 2-coloring with matrix A2,4 exists. Then, since s11 = s22 = 3, the subgraph of G induced by the set of white vertices is 3-regular, as is the subgraph of G induced by the set of black vertices. On the other hand, s12 = s21 = 1. Thus the number of white vertices is even and equals the number of black vertices. Therefore, the order of G must be a multiple of 4.
We now show that A2,4 is admissible only for G = Cn□Cm with m ≡ 0 (mod 4). Since G is vertex-transitive and Cn□Cm ≅ Cm□Cn, without loss of generality, vertex (0, 0) is black and vertex (0, 1) is white, as shown in Figure 3. Every white vertex has one black neighbor and every black vertex has one white neighbor. So the vertices (1, 0), (n − 1, 0), (0, m − 1) are black and the vertices (1, 1), (n − 1, 1), (0, 2) are white. Continuing in this way, the vertices on cycles {(i, 0)|0 ≤ i ≤ n − 1} and {(i, m − 1)|0 ≤ i ≤ n − 1} are black, and vertices on cycles {(i, 1)|0 ≤ i ≤ n − 1} and {(i, 2)|0 ≤ i ≤ n − 1} are white. Assuming m ≡ 0 (mod 4), this coloring can uniquely be extended to other vertices. Let W = {(i, j)| j ≡ 1 or 2 (mod 4)} and B = V(G)W. Then, every vertex in W has three neighbors in W and one neighbor in B, and every vertex in B has one neighbor in W and three neighbors in B. This is a perfect 2-coloring with matrix A2,4.
Theorem 3.3
Let 3 ≤ n, m < ∞. The toroidal grid G = Cn□Cm admits a perfect 2-coloring with matrix A3,3if and only if m ≡ 0 (mod 2).
Proof
Suppose a perfect 2-coloring with matrix A3,3 exists. Then, since s12 = s21, we have by Lemma 2.2 that the number of white vertices is equal to the number of black vertices. So the order of G must be even. Therefore m (or n) must be even. Let m ≡ 0 (mod 2). The sets W = {(i, j)| j ≡ 0 (mod 2)} and B = V(G) W give us a perfect 2-coloring with matrix A3,3. The coloring of a part of graph is shown in Figure 4.
Theorem 3.4
Let 3 ≤ n, m < ∞. The toroidal grid G = Cn□Cm admits a perfect 2-coloring with matrix A3,4if and only if m ≡ 0 (mod 3).
Proof
Suppose a perfect 2-coloring with matrix A3,4 exists. Then, since s12 = 2 and s21 = 1, we have by Lemma 2.2 that 2w = b where w is the number of white vertices and b is the number of black vertices. So the order of G must be a multiple of 3. Therefore m (or n) must be a multiple of 3. Let m ≡ 0 (mod 3). The sets W = {(i, j)| j ≡ 1 (mod 3)} and B = V(G) W give us a perfect 2-coloring with matrix A3,4. The coloring of a part of graph is shown in Figure 5.
Theorem 3.5
Let 3 ≤ n, m < ∞. The toroidal grid G = Cn□Cm admits a perfect 2-coloring with matrix A4,2if and only if n ≡ 0 (mod 4) and m ≡ 0 (mod 2).
Proof
Suppose A4,2 is admissible for G. By Lemma 2.3, the order of G must be a multiple of 4. But this condition is not sufficient. We will show that the sufficient condition for the existence of this coloring is that n ≡ 0 (mod 4) and m ≡ 0 (mod 2).
Every white vertex has one white neighbor. According to the structure of graph, without loss of generality the vertices (0, 0) and (1, 0) are white, as shown in Figure 6. So the vertices (0, 1), (1, 1), (2, 0), (0, m − 1), (1, m − 1), (n − 1, 0) are all black. Since (2, 1) is adjacent to two black vertices (1, 1), (2, 0), it must be white. Similarly, (2, m − 1) is also white. Now consider (3, 0). The vertex (2, 0) has three white neighbors, (2, 1), (1, 0), (2, m−1), so (3, 0) is black. This vertex has one black neighbor, so its other neighbors, (4, 0), (3, 1), (3, m − 1) are white. Continuing we find that in each cycle of length n, every vertex has one neighbor of the same color, and in each cycle of length m, the color of verticies changes alternately. Therefore to complete the coloring we must have n ≡ 0 (mod 4) and m ≡ 0 (mod 2).
Theorem 3.6
Let 3 ≤ n, m < ∞. The toroidal grid G = Cn□Cm admits a perfect 2-coloring with matrix A4,3if and only if m, n ≡ 0 (mod 5).
Proof
We specify the colors of the vertices of a 5×5 grid and show that this pattern repeats in each consecutive 5 × 5 grid on n-cycles and m-cycles.
Since G is vertex-transitive, without loss of generality (0, 0) and (1, 0) are white, as shown in Figure 7. So since s11 = 1, their neighbors, (n − 1, 0), (0, m − 1), (0, 1), (1, m−1), (1, 1), (2, 0) are all black. The vertex (1, 1) is black and must have two black neighbors. So one of the vertices (2, 1) and (1, 2) is black. Without loss of generality, (2, 1) is black. The vertices (1, 1) and (2, 1) have two black neighbors, so the vertices (1, 2) and (2, 2) are white and their neighbors, (0, 2), (1, 3), (2, 3), (3, 2) are all black. Also, the vertex (3, 1) is white. Thus, the black vertex (3, 2) has two white neighbors and so (3, 3) is black. Similarly, the vertices (2, 3) and (3, 3) have two black neighbors, so the vertices (2, 4) and (3, 4) are white and (1, 4) is black. Now consider (0, 3). Since the black vertex (1, 3) has two black neighbors, the vertex (0, 3) is white and so (n − 1, 2) is black. Since (n − 1, 1) has three black neighbors, this vertex and its fourth neighbor, (n − 2, 1), are white. Therefore, (n − 2, 2) is black and (n − 1, 3) is white. Also, the vertex (n − 1, m − 1) is black. Arguing in the same way, the vertices (2, m − 1) and (3, m − 1) are white and (3, 0) is black.
Continuing we specify the color of other vertices and find that the pattern of 5 × 5 grid with vertices {(i, j)|i = n − 1, 0, 1, 2, 3;, j = m − 1, 0, 1, 2, 3} repeats in each consecutive 5 × 5 grid on n-cycles and m-cycles. So to complete the coloring we must have m, n ≡ 0 (mod 5).
Definition 3.7
A set S ⊆ V(G) is called a total dominating set if each vertex v ∈ V(G) is adjacent to a vertex in S. A total dominating set S is called efficient, if every vertex v ∈ V(G) is adjacent to exactly one vertex in S.
The above definition immediately implies that G admits a perfect 2-coloring with matrix A4,4 if and only if G has an efficient total dominating set. Dejter [4] referred to a efficient total dominating set as a total perfect code. If the induced components of a total perfect code in a grid graph are pairwise parallel edges, then the code is called parallel. Similarly, we call a perfect 2-coloring with matrix A4,4 in toroidal grid parallel, if the edges with white ends are parallel. So we have the following theorem:
Theorem 3.8
Let 3 ≤ n, m < ∞. The toroidal grid G = Cn□Cm admits a parallel perfect 2-coloring with matrix A4,4if and only if m, n ≡ 0 (mod 4).
The coloring of a part of graph with matrix A4,4 is shown in Figure 8.
Theorem 3.9
Let 3 ≤ n, m < ∞. The toroidal grid G = Cn□Cm admits a perfect 2-coloring with matrix A5,1if and only if m, n ≡ 0 (mod 2).
Proof
A graph admits a perfect 2-coloring with matrix A5,1 if and only if it is bipartite. A toroidal grid G = Cn□Cm is bipartite if and only if m, n ≡ 0 (mod 2). Let W = {(i, j)| i, j ≡ 0 (mod 2)} ∪ {(i, j)| i, j ≡ 1 (mod 2)} and B = V(G) W. Clearly (W, B) is a bipartition of G, and therefore gives us a perfect 2-coloring with matrix A5,1. The coloring of a part of the graph is shown in Figure 9.
Theorem 3.10
Let 3 ≤ n, m < ∞. The toroidal grid G = Cn□Cm does not admit a perfect 2-coloring with matrix A5,2.
Proof
Suppose a perfect 2-coloring with matrix A5,2 exists. Then, since s11 = 0 and s22 = 1, the neighbors of each white vertex are all black, and every black vertex has exactly one black neighbor. Since G is vertex-transitive and Cn□Cm ≅ Cm□Cn, without loss of generality, (0, 0) and (1, 0) are black. So their neighbors, (0, 1), (1, 1), (n − 1, 0), (2, 0), (0, m − 1), (1, m − 1), are all white. According to the structure of the graph, this contradicts that the set of white vertices is independent. Because, (0, 1) is adjacent to (1, 1), and also (0, m−1) is adjacent to (1, m−1).
Theorem 3.11
Let 3 ≤ n, m < ∞. The toroidal grid G = Cn□Cm admits a perfect 2-coloring with matrix A5,3if and only if m, n ≡ 0 (mod 3).
Proof
As shown in Figure 10, we specify the colors of the vertices of a 3×3 grid with vertices {(i, j)|i = n − 1, 0, 1; j = m − 1, 0, 1} (the details are similar to the proof of Theorem 3.6). Continuing we can specify the color of other vertices and find that this pattern repeats in each consecutive 3×3 grid on n-cycles and m-cycles. So the necessary and sufficient condition for the existence of this coloring is that m, n ≡ 0 (mod 3).
Theorem 3.12
Let 3 ≤ n, m < ∞. The toroidal grid G = Cn□Cm admits a perfect 2-coloring with matrix A5,4if and only if m, n ≡ 0 (mod 5).
Proof
As in the proof of Theorem 3.11, we can specify the colors of the vertices of a 5 × 5 grid and show that this pattern repeats in each consecutive 5 × 5 grid on n-cycles and m-cycles. So the necessary and sufficient condition for the existence of this coloring is that m, n ≡ 0 (mod 5). The coloring of a part of graph is shown in Figure 11.
