Perfect 3-colorings of the cubic graphs of order 10

Mehdi Alaeiyan, Ayoob Mehrabani

School of Mathematics, Iran University of Science and Technology, Narmak, Tehran 16846, Iran

alaeiyan@iust.ac.ir, amehrabani@mathdep.iust.ac.ir

Perfect coloring is a generalization of the notion of completely regular codes, given by Delsarte. A perfect m-coloring of a graph G with m colors is a partition of the vertex set of G into m parts A1, A2, · · · , A^m such that, for all i, j ∈ {1, · · · , m}, every vertex of Aⁱ is adjacent to the same number of vertices, namely, aij vertices, of A^j . The matrix A = (aij )i,j∈{1,··· ,m} is called the parameter matrix. We study the perfect 3-colorings (also known as the equitable partitions into three parts) of the cubic graphs of order 10. In particular, we classify all the realizable parameter matrices of perfect 3-colorings for the cubic graphs of order 10.

Keywords: perfect coloring, equitable partition, cubic graph Mathematics Subject Classification: 03E02, 05C15, 68R05 DOI:10.5614/ejgta.2017.5.2.3

1. Introduction

The concept of a perfect m-coloring plays an important role in graph theory, algebraic combinatorics, and coding theory (completely regular codes). There is another term for this concept in the literature as "equitable partition" (see[10]).

The existence of completely regular codes in graphs is a historical problem in mathematics. Completely regular codes are a generalization of perfect codes. In 1973, Delsarte conjectured the non-existence of nontrivial perfect codes in Johnson graphs. Therefore, some effort has been done

Received: 12 November 2016, Revised: 19 May 2017, Accepted: 30 June 2017.

on enumerating the parameter matrices of some Johnson graphs, including J(4, 2), J(5, 2), J(6, 2), J(6, 3), J(7, 3), J(8, 3), J(8, 4), and J(v, 3) (v odd) (see [1, 3, 4, 9]).

Fon-Der-Flass enumerated the parameter matrices (perfect 2-colorings) of n-dimensional hypercube Qⁿ for n < 24. He also obtained some constructions and a necessary condition for the existence of perfect 2-colorings of the n-dimensional cube with a given parameter matrix (see [6, 7, 8]). In this paper all graphs are assumed simple, connected and undirected. First we give some basic definitions and concepts. Let G = (V, E) be a graph. Two vertices u, v ∈ V (G) are adjacent if there exists an edge e = {u, v} ∈ E(G) to which they are both incident. The adjacent will be shown u ↔ v.

A cubic graph is a 3-regular graph. In [5], it is shown that the number of connected cubic graphs with 10 vertices is 19. Each graph is described by a drawing as shown in Figure 1.

Figure 1. Connected cubic graphs of order 10.

Definition 1.1. For a graph G and a positive integer m, a mapping T : V (G) → {1, · · · , m} is called a perfect m-coloring with matrix A = (aij )i,j∈{1,··· ,m}, if it is surjective, and for all i, j, for every vertex of color i, the number of its neighbors of color j is equal to aij . The matrix A is called the parameter matrix of a perfect coloring. In the case m = 3, we call the first color white, the second color black, and the third color red. In this paper, we generally show a parameter matrix by

\[A = \begin{bmatrix} a & b & c \\ d & e & f \\ g & h & i \end{bmatrix}.\]

Remark 1.1. In this paper, we consider all perfect 3-colorings, up to renaming the colors; i.e. we identify the perfect 3-coloring with the matrices

\[\begin{bmatrix} a & c & b \\ g & i & h \\ d & f & e \end{bmatrix}, \begin{bmatrix} e & d & f \\ b & a & c \\ h & g & i \end{bmatrix}, \qquad \begin{bmatrix} e & f & d \\ h & i & g \\ b & c & a \end{bmatrix}, \begin{bmatrix} i & h & g \\ f & e & d \\ c & b & a \end{bmatrix}, \begin{bmatrix} i & g & h \\ c & a & b \\ f & d & e \end{bmatrix},\]

obtained by switching the colors with the original coloring.

2. Preliminaries and Analysis

In this section, we present some results concerning necessary conditions for the existence of perfect 3-colorings of a cubic connected graph of order 10 with a given parameter matrix

\[A = \begin{bmatrix} a & b & c \\ d & e & f \\ g & h & i \end{bmatrix}.\]

The simplest necessary condition for the existence of perfect 3-colorings of a cubic connected

graph with the matrix a b c d e f g h i is:

\[a + b + c = d + e + f = g + h + i = 3.\]

Also, it is clear that we cannot have b = c = 0, d = f = 0, or g = h = 0, since the graph is connected. In addition, b = 0, c = 0, f = 0 if d = 0, g = 0, h = 0, respectively.

The number θ is called an eigenvalue of a graph G, if θ is an eigenvalue of the adjacency matrix of this graph. The number θ is called an eigenvalue of a perfect coloring T into three colors with the matrix A, if θ is an eigenvalue of A. The following lemma demonstrates the connection between the introduced notions.

Lemma 2.1. [10] If T is a perfect coloring of a graph G in m colors, then any eigenvalue of T is an eigenvalue of G.

Now, without lost of generality, we can assume that |W| ≤ |B| ≤ |R|. The following proposition gives us the size of each class of color.

.

Proposition 2.1. Let T be a perfect 3-coloring of a graph G with the matrix A = a b c d e f g h i .

1. If b, c, f 6= 0, then

\[|W| = \frac{|V(G)|}{\frac{b}{d} + 1 + \frac{c}{g}}, |B| = \frac{|V(G)|}{\frac{d}{b} + 1 + \frac{f}{h}}, |R| = \frac{|V(G)|}{\frac{h}{f} + 1 + \frac{g}{c}}\]

2. If b = 0, then

\[|W| = \frac{|V(G)|}{\frac{c}{g} + 1 + \frac{ch}{fg}}, |B| = \frac{|V(G)|}{\frac{f}{h} + 1 + \frac{fg}{ch}}, |R| = \frac{|V(G)|}{\frac{h}{f} + 1 + \frac{g}{c}}.\]

3. If c = 0, then

\[|W| = \frac{|V(G)|}{\frac{b}{d} + 1 + \frac{bf}{dh}}, |B| = \frac{|V(G)|}{\frac{d}{b} + 1 + \frac{f}{h}}, |R| = \frac{|V(G)|}{\frac{h}{f} + 1 + \frac{dh}{bf}}.\]

4. If f = 0, then

\[|W| = \frac{|V(G)|}{\frac{b}{d} + 1 + \frac{c}{g}}, |B| = \frac{|V(G)|}{\frac{d}{b} + 1 + \frac{cd}{bg}}, |R| = \frac{|V(G)|}{\frac{g}{c} + 1 + \frac{bg}{cd}}.\]

Proof. (1): Consider the 3-partite graph obtained by removing the edges uv such that u and v are the same color. By counting the number of edges between parts, we can easily obtain |W|b = |B|d, |W|c = |R|g, and |B|f = |R|h. Now, we can conclude the desired result from |W| + |B| + |R| = |V (G)|.

The proof of (2), (3), (4) is similar to (1).

In the next lemma, under the condition |W| = 1, we enumerate all matrices that can be a parameter matrix for a cubic connected graph.

Lemma 2.2. Let G be a cubic connected graph of order 10. If T is a perfect 3-coloring with the matrix A, and |W| = 1, then A should be the following matrix:

\[A = \begin{bmatrix} 0 & 3 & 0 \\ 1 & 0 & 2 \\ 0 & 1 & 2 \end{bmatrix}.\]

Proof. Let A = a b c d e f g h i be a parameter matrix with ^|W^| = 1. Consider the white vertex. It is clear that none of its adjacent vertices are white; i.e. a = 0. Therefore, we have two cases below.

(1) The adjacent vertices of the white vertex are the same color. If they are black, then b = 3 and c = 0. From c = 0, we get g = 0. Also, since the graph is connected, we have f, h 6= 0. Hence we obtain the following matrices:

\[\begin{bmatrix} 0 & 3 & 0 \\ 1 & 1 & 1 \\ 0 & 1 & 2 \end{bmatrix}, \begin{bmatrix} 0 & 3 & 0 \\ 1 & 0 & 2 \\ 0 & 1 & 2 \end{bmatrix}, \begin{bmatrix} 0 & 3 & 0 \\ 1 & 0 & 2 \\ 0 & 2 & 1 \end{bmatrix}, \begin{bmatrix} 0 & 3 & 0 \\ 1 & 1 & 1 \\ 0 & 2 & 1 \end{bmatrix}, \begin{bmatrix} 0 & 3 & 0 \\ 1 & 0 & 2 \\ 0 & 3 & 0 \end{bmatrix}, \begin{bmatrix} 0 & 3 & 0 \\ 1 & 1 & 1 \\ 0 & 3 & 0 \end{bmatrix}.\]

If the adjacent vertices of the white vertex are red, then c = 3, b = 0. From b = 0, we get d = 0. Also, since the graph is connected, we have f, h 6= 0. Hence we obtain the following matrices:

\[\begin{bmatrix} 0 & 0 & 3 \\ 0 & 1 & 2 \\ 1 & 1 & 1 \end{bmatrix}, \begin{bmatrix} 0 & 0 & 3 \\ 0 & 1 & 2 \\ 1 & 2 & 0 \end{bmatrix}, \begin{bmatrix} 0 & 0 & 3 \\ 0 & 2 & 1 \\ 1 & 1 & 1 \end{bmatrix}, \begin{bmatrix} 0 & 0 & 3 \\ 0 & 2 & 1 \\ 1 & 2 & 0 \end{bmatrix}, \begin{bmatrix} 0 & 0 & 3 \\ 0 & 0 & 3 \\ 1 & 1 & 1 \end{bmatrix}, \begin{bmatrix} 0 & 0 & 3 \\ 0 & 0 & 3 \\ 1 & 2 & 0 \end{bmatrix}.\]

Finally, by using Remark 1.1 and the fact that |W| ≤ |B| ≤ |R|, it is obvious that there are only six matrices in (1), as shown A1, A2, A3, A4, A5, A6.

\[A_{1} = \begin{bmatrix} 0 & 3 & 0 \\ 1 & 1 & 1 \\ 0 & 1 & 2 \end{bmatrix}, A_{2} = \begin{bmatrix} 0 & 3 & 0 \\ 1 & 0 & 2 \\ 0 & 1 & 2 \end{bmatrix}, A_{3} = \begin{bmatrix} 0 & 3 & 0 \\ 1 & 0 & 2 \\ 0 & 2 & 1 \end{bmatrix}, A_{4} = \begin{bmatrix} 0 & 0 & 3 \\ 0 & 1 & 2 \\ 1 & 1 & 1 \end{bmatrix},\] \[A_{5} = \begin{bmatrix} 0 & 0 & 3 \\ 0 & 0 & 3 \\ 1 & 1 & 1 \end{bmatrix}, A_{6} = \begin{bmatrix} 0 & 0 & 3 \\ 0 & 0 & 3 \\ 1 & 2 & 0 \end{bmatrix}\]

(2) The adjacent vertices of the white vertex are different colors. It immediately gives that b, c 6= 0. Also, it can be seen that d = g = 1. An easy computation as in (1), shows that there are only five matrices that can be a parameter matrix in this case, as shown A7, A8, A9, A10, A11.

\[A_{7} = \begin{bmatrix} 0 & 1 & 2 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{bmatrix}, A_{8} = \begin{bmatrix} 0 & 2 & 1 \\ 1 & 0 & 2 \\ 1 & 1 & 1 \end{bmatrix}, A_{9} = \begin{bmatrix} 0 & 1 & 2 \\ 1 & 2 & 0 \\ 1 & 0 & 2 \end{bmatrix}, A_{10} = \begin{bmatrix} 0 & 1 & 2 \\ 1 & 0 & 2 \\ 1 & 1 & 1 \end{bmatrix},\] \[A_{11} = \begin{bmatrix} 0 & 1 & 2 \\ 1 & 0 & 2 \\ 1 & 2 & 0 \end{bmatrix}.\]

By using Proposition 2.1, it is obvious that just the matrix A := A² can be a parameter.

Lemma 2.3. Let G be a cubic connected graph of order 10. If T is a perfect 3-coloring with the matrix A, and |W| = |B| = 2, |R| = 6, then A should be the following matrix

\[\begin{bmatrix} 0 & 0 & 3 \\ 0 & 0 & 3 \\ 1 & 1 & 1 \end{bmatrix}.\]

Proof. First, suppose that \(b, c \neq 0\). As |W| = 2, by Proposition 2.1, it follows that \(\frac{b}{d} + \frac{c}{c} = 4\). Therefore b = c = 2, d = g = 1 and we get a contradiction with \(b + c \le 3\).

Second, suppose that b=0 and then d=0. As |R|=4, by Proposition 2.1, we have \(\frac{g}{c}+\frac{h}{f}=\frac{2}{3}\).

Therefore c=f=3, g=h=1, and consequently \(A=\begin{bmatrix}0&0&3\\0&0&3\\1&1&1\end{bmatrix}.\)

Finally, suppose that c=0 and then g=0. As |B|=2, by Proposition 2.1, it follows that

\[\frac{d}{b} + \frac{f}{h} = 4. \text{ Therefore } b = f = 2, d = h = 1, \text{ or } b = 3, d = f = h = 1 \text{ or } b = 3, d = 1,\] \[f = h = 2. \text{ Hence } A = \begin{bmatrix} 1 & 2 & 0 \\ 1 & 0 & 2 \\ 0 & 1 & 2 \end{bmatrix}, \text{ or } A = \begin{bmatrix} 0 & 3 & 0 \\ 1 & 1 & 1 \\ 0 & 1 & 2 \end{bmatrix}, \text{ or } A = \begin{bmatrix} 0 & 3 & 0 \\ 1 & 0 & 2 \\ 0 & 2 & 1 \end{bmatrix}.\]

By using the Proposition 2.1, it can be seen that only the matrix \(\begin{bmatrix} 0 & 0 & 3 \\ 0 & 0 & 3 \\ 1 & 1 & 1 \end{bmatrix}\) can be a parameter. \(\Box\)

Lemma 2.4. Let G be a cubic connected graph of order 10. Then G has no perfect 3-coloring T with the matrix that |W| = 2, |B| = 3, |R| = 5.

Proof. If T is a perfect 3-coloring with the similar proving Lemma 2.3, A should be one of the following matrices:

\[\begin{bmatrix} 2 & 0 & 1 \\ 0 & 1 & 2 \\ 1 & 1 & 1 \end{bmatrix}, \begin{bmatrix} 1 & 0 & 2 \\ 0 & 2 & 1 \\ 1 & 1 & 1 \end{bmatrix}, \begin{bmatrix} 1 & 0 & 2 \\ 0 & 1 & 2 \\ 2 & 1 & 0 \end{bmatrix}, \begin{bmatrix} 1 & 0 & 2 \\ 0 & 1 & 2 \\ 1 & 2 & 0 \end{bmatrix}, \begin{bmatrix} 1 & 0 & 2 \\ 0 & 1 & 2 \\ 1 & 2 & 0 \end{bmatrix}, \begin{bmatrix} 1 & 2 & 0 \\ 1 & 1 & 1 \\ 0 & 2 & 1 \end{bmatrix}, \begin{bmatrix} 1 & 2 & 0 \\ 2 & 0 & 1 \\ 0 & 2 & 1 \end{bmatrix}, \begin{bmatrix} 1 & 2 & 0 \\ 1 & 0 & 2 \\ 0 & 2 & 1 \end{bmatrix}.\]

By using the Proposition 2.1, it can be seen that no matrix can be a parameter.

Lemma 2.5. Let G be a cubic connected graph of order 10. If T is a perfect 3-coloring with the matrix A, and also if |W| = 2, |B| = 4, |R| = 4, then A should be one of the following matrices:

\[\begin{bmatrix} 1 & 0 & 2 \\ 0 & 2 & 1 \\ 1 & 1 & 1 \end{bmatrix}, \begin{bmatrix} 1 & 0 & 2 \\ 0 & 1 & 2 \\ 1 & 2 & 0 \end{bmatrix}, \begin{bmatrix} 1 & 2 & 0 \\ 1 & 1 & 1 \\ 0 & 1 & 2 \end{bmatrix}, \begin{bmatrix} 1 & 2 & 0 \\ 1 & 0 & 2 \\ 0 & 2 & 1 \end{bmatrix}.\]

Proof. If T is a perfect 3-coloring with the similar proving Lemma2.3, then A should be one of the following matrices:

\[\begin{bmatrix} 2 & 0 & 1 \\ 0 & 1 & 2 \\ 1 & 1 & 1 \end{bmatrix}, \begin{bmatrix} 1 & 0 & 2 \\ 0 & 2 & 1 \\ 1 & 1 & 1 \end{bmatrix}, \begin{bmatrix} 1 & 0 & 2 \\ 0 & 1 & 2 \\ 2 & 1 & 0 \end{bmatrix}, \begin{bmatrix} 1 & 0 & 2 \\ 0 & 1 & 2 \\ 1 & 2 & 0 \end{bmatrix}, \begin{bmatrix} 1 & 0 & 2 \\ 0 & 1 & 2 \\ 1 & 2 & 0 \end{bmatrix}, \begin{bmatrix} 1 & 2 & 0 \\ 1 & 1 & 1 \\ 0 & 2 & 1 \end{bmatrix}, \begin{bmatrix} 1 & 2 & 0 \\ 2 & 0 & 1 \\ 0 & 2 & 1 \end{bmatrix}, \begin{bmatrix} 1 & 2 & 0 \\ 1 & 0 & 2 \\ 0 & 2 & 1 \end{bmatrix}.\]

By using the Proposition 2.1, it can be seen that the following matrices should be parameter:

\[\begin{bmatrix} 1 & 0 & 2 \\ 0 & 2 & 1 \\ 1 & 1 & 1 \end{bmatrix}, \begin{bmatrix} 1 & 0 & 2 \\ 0 & 1 & 2 \\ 1 & 2 & 0 \end{bmatrix}, \begin{bmatrix} 1 & 2 & 0 \\ 1 & 1 & 1 \\ 0 & 1 & 2 \end{bmatrix}, \begin{bmatrix} 1 & 2 & 0 \\ 1 & 0 & 2 \\ 0 & 2 & 1 \end{bmatrix}.\]

Lemma 2.6. Let G be a cubic connected graph of order 10. Then G has no perfect 3-coloring T with the matrix that |W| = 3, |B| = 3, |R| = 4.

Proof. If T is a perfect 3-coloring with the similar proving Lemma2.3, then A should be one of the following matrices:

\[\begin{bmatrix} 0 & 1 & 2 \\ 3 & 0 & 0 \\ 1 & 0 & 2 \end{bmatrix}, \begin{bmatrix} 0 & 2 & 1 \\ 1 & 2 & 0 \\ 3 & 0 & 0 \end{bmatrix}, \begin{bmatrix} 2 & 0 & 1 \\ 0 & 1 & 2 \\ 1 & 1 & 1 \end{bmatrix}, \begin{bmatrix} 1 & 0 & 2 \\ 0 & 2 & 1 \\ 1 & 1 & 1 \end{bmatrix}, \begin{bmatrix} 1 & 0 & 2 \\ 0 & 1 & 2 \\ 1 & 2 & 0 \end{bmatrix}, \begin{bmatrix} 1 & 0 & 2 \\ 0 & 1 & 2 \\ 2 & 1 & 0 \end{bmatrix}, \begin{bmatrix} 0 & 3 & 0 \\ 1 & 0 & 2 \\ 0 & 1 & 2 \end{bmatrix}, \begin{bmatrix} 2 & 1 & 0 \\ 2 & 0 & 1 \\ 0 & 3 & 0 \end{bmatrix}.\]

By using Proposition 2.1, it can be seen that no matrix can be a parameter.

By using Lemmas 2.2, 2.3 and 2.5, it can be seen that only the following matrices can be parameter ones.

\[\begin{bmatrix} 0 & 0 & 3 \\ 0 & 0 & 3 \\ 1 & 1 & 1 \end{bmatrix}, \begin{bmatrix} 1 & 0 & 2 \\ 0 & 2 & 1 \\ 1 & 1 & 1 \end{bmatrix}, \begin{bmatrix} 1 & 0 & 2 \\ 0 & 1 & 2 \\ 1 & 2 & 0 \end{bmatrix}, \begin{bmatrix} 1 & 2 & 0 \\ 1 & 1 & 1 \\ 0 & 1 & 2 \end{bmatrix}, \begin{bmatrix} 1 & 2 & 0 \\ 1 & 0 & 2 \\ 0 & 2 & 1 \end{bmatrix}, \begin{bmatrix} 0 & 3 & 0 \\ 1 & 0 & 2 \\ 0 & 1 & 2 \end{bmatrix}.\]

By Remark 1.1, it is clear that the matrix 1 0 2 0 2 1 1 1 1 is the same as the matrix 1 2 0 1 1 1 0 1 2 and the

matrix 1 0 2 0 1 2 1 2 0 is the same as the matrix 1 2 0 1 0 2 0 2 1 up to renaming the colors. Therefore, if ^T

is a perfect 3-coloring with the matrix A , then A should be one of the following matrices:

\[A_1 = \begin{bmatrix} 0 & 0 & 3 \\ 0 & 0 & 3 \\ 1 & 1 & 1 \end{bmatrix}, A_2 = \begin{bmatrix} 1 & 0 & 2 \\ 0 & 2 & 1 \\ 1 & 1 & 1 \end{bmatrix}, A_3 = \begin{bmatrix} 1 & 0 & 2 \\ 0 & 1 & 2 \\ 1 & 2 & 0 \end{bmatrix}, A_4 = \begin{bmatrix} 0 & 3 & 0 \\ 1 & 0 & 2 \\ 0 & 1 & 2 \end{bmatrix}.\]

The next theorem can be useful to find the eigenvalues of a parameter matrix.

Theorem 2.1. Let A = a b c d e f g h i be a parameter matrix of a ^k-regular graph. Then the eigenvalues of A are

\[\lambda_{1,2} = \frac{\operatorname{tr}(A) - k}{2} \pm \sqrt{\left(\frac{\operatorname{tr}(A) - k}{2}\right)^2 - \frac{\det(A)}{k}} , \quad \lambda_3 = k.\]

Proof. By using the condition a + b + c = d + e + f = g + h + i = k, it is clear that one of the eigenvalues is k. Therefore det(A) = kλ1λ2. From λ² = tr (A) − λ¹ − k, we get

\[\det(A) = k\lambda_1(\operatorname{tr}(A) - \lambda_1 - k) = -k\lambda_1^2 + k(\operatorname{tr}(A) - k)\lambda_1.\]

By solving the equation λ ² + (k − tr (A))λ + det(A) k = 0, we obtain

\[\lambda_{1,2} = \frac{\operatorname{tr}(A) - k}{2} \pm \sqrt{\left(\frac{\operatorname{tr}(A) - k}{2}\right)^2 - \frac{\det(A)}{k}}.\]

3. Perfect 3-colorings of the cubic connected graphs of order 10

In this section, we enumerate the parameter matrices of all perfect 3-colorings of the cubic connected graphs of order 10.

Theorem 3.1. The parameter matrices of cubic graphs of order 10 are listed in the following table.

Table 1

Proof. As it has been shown in Section 3, only matrices \(A_1\), \(A_2\), \(A_3\) and \(A_4\) can be parameter matrices. With consideration of cubic graphs eigenvalues and using Theorem 2.1, it can be seen that the connected cubic graphs with 10 vertices can have perfect 3-coloring with matrices \(A_1\), \(A_2\), \(A_3\) and \(A_4\) which is represented by Table 2.

Table 2

The vertices of cubic graphs are labeled clockwise with \(a_1, a_2, ..., a_{10}\), respectively. The graph 1 has perfect 3-colorings with the matrices \(A_1\) and \(A_3\). Consider two mappings \(T_1\) and \(T_2\) as follows:

Perfect 3-colorings of the cubic graphs of order 10 | M. Alaeiyan and A. Mehrabani

\[T_1(a_1) = T_1(a_{10}) = 1, T_1(a_4) = T_1(a_7) = 2,\]
\(T_1(a_2) = T_1(a_3) = T_1(a_5) = T_1(a_6) = T_1(a_8) = T_1(a_9) = 3.\)
\(T_2(a_5) = T_2(a_6) = 1, T_2(a_2) = T_2(a_3) = T_2(a_8) = T_2(a_9) = 2,\)
\(T_2(a_1) = T_2(a_4) = T_2(a_7) = T_2(a_3) = 3.\)

It is clear that T¹ and T² are perfect 3-coloring with the matrices A¹ and A3, respectively.

The graph 2 has perfect 3-colorings with the matrices A1, A³ and A4. Consider three mappings T1, T² and T³ as follows:

\[T_1(a_2) = T_1(a_7) = 1, T_1(a_5) = T_1(a_{10}) = 2,\] \[T_1(a_1) = T_1(a_3) = T_1(a_4) = T_1(a_6) = T_1(a_8) = T_1(a_9) = 3.\] \[T_2(a_1) = T_2(a_6) = 1, T_2(a_3) = T_2(a_4) = T_2(a_8) = T_2(a_9) = 2,\] \[T_2(a_2) = T_2(a_5) = T_2(a_7) = T_2(a_{10}) = 3.\] \[T_3(a_1) = 1, T_3(a_2) = T_3(a_6) = T_3(a_{10}) = 2,\] \[T_3(a_3) = T_3(a_4) = T_3(a_5) = T_3(a_7) = T_3(a_8) = T_3(a_9) = 3.\]

It is clear that T1, T² and T³ are perfect 3-coloring with the matrices A1, A³ and A4, respectively.

The graph 4 has perfect 3-colorings with the matrix A1. Consider the mapping T¹ as follows:

\[T_1(a_5) = T_1(a_{10}) = 1, T_1(a_2) = T_1(a_7) = 2,\]
\(T_1(a_1) = T_1(a_3) = T_1(a_4) = T_1(a_6) = T_1(a_8) = T_1(a_9) = 3.\)

It is clear that T¹ is a perfect 3-coloring with the matrix A1.

The graph 6 has perfect 3-colorings with the matrices A¹ and A3. Consider two mappings T¹ and T² as follows:

\[T_1(a_5) = T_1(a_9) = 1, T_1(a_7) = T_1(a_2) = 2,\] \(T_1(a_1) = T_1(a_3) = T_1(a_4) = T_1(a_6) = T_1(a_8) = T_1(a_{10}) = 3.\) \(T_2(a_3) = T_2(a_4) = 1, T_2(a_1) = T_2(a_6) = 2 = T_2(a_8) = T_2(a_{10}) = 2,\) \(T_2(a_2) = T_2(a_5) = T_2(a_7) = T_2(a_9) = 3.\)

It is clear that T¹ and T² are perfect 3-coloring with the matrices A¹ and A3, respectively.

The graph 9 has perfect 3-colorings with the matrices A³ and A4. Consider two mappings T¹ and T² as follows:

\[T_1(a_1) = T_1(a_6) = 1, T_1(a_3) = T_1(a_4) = T_1(a_8) = T_1(a_9) = 2,\]
\(T_1(a_2) = T_1(a_5) = T_1(a_7) = T_1(a_{10}) = 3.\)
\(T_2(a_1) = 1, T_2(a_2) = T_2(a_6) = 2 = T_2(a_{10}) = 2,\)
\(T_2(a_3) = T_2(a_4) = T_2(a_5) = T_2(a_7) = T_2(a_8) = T_2(a_9) = 3.\)

It is clear that T¹ and T² are perfect 3-coloring with the matrices A³ and A4, respectively.

The graph 10 has perfect 3-colorings with the matrices A¹ and A3. Consider two mappings T¹ and T² as follows:

\[T_1(a_2) = T_1(a_5) = 1, T_1(a_7) = T_1(a_{10}) = 2,\]
\(T_1(a_1) = T_1(a_3) = T_1(a_4) = T_1(a_6) = T_1(a_8) = T_1(a_9) = 3.\)
\(T_2(a_1) = T_2(a_6) = 1, T_2(a_3) = T_4(a_6) = 2 = T_2(a_8) = T_2(a_9) = 2,\)
\(T_2(a_2) = T_2(a_5) = T_2(a_7) = T_2(a_{10}) = 3.\)

It is clear that T¹ and T² are perfect 3-coloring with the matrices A¹ and A3, respectively.

The graph 13 has perfect 3-colorings with the matrix A4. Consider a mapping T¹ as follows:

\[T_1(a_6) = 1, T_1(a_1) = T_1(a_5) = T_1(a_7) = 2,\]
\(T_1(a_2) = T_1(a_3) = T_1(a_4) = T_1(a_7) = T_1(a_8) = T_1(a_9) = 3.\)

It is clear that T¹ is a perfect 3-coloring with the matrix A4.

The graph 14 has perfect 3-colorings with the matrix A4. Consider a mapping T¹ as follows:

\[T_1(a_6) = 1, T_1(a_1) = T_1(a_5) = T_1(a_7) = 2,\]
\(T_1(a_2) = T_1(a_3) = T_1(a_4) = T_1(a_7) = T_1(a_8) = T_1(a_9) = 3.\)

It is clear that T¹ is a perfect 3-coloring with the matrix A4.

The graph 18 has perfect 3-colorings with the matrices A³ and A4. Consider two mappings T¹ and T² as follows:

\[T_1(a_1) = T_1(a_6) = 1, T_1(a_3) = T_1(a_4) = T_1(a_8) = T_1(a_9) = 2,\]
\(T_1(a_2) = T_1(a_5) = T_1(a_7) = T_1(a_{10}) = 3.\)
\(T_2(a_1) = 1, T_2(a_2) = T_2(a_6) = 2 = T_2(a_{10}) = 2,\)
\(T_2(a_3) = T_2(a_4) = T_2(a_5) = T_2(a_7) = T_2(a_8) = T_2(a_9) = 3.\)

It is clear that T¹ and T² are perfect 3-coloring with the matrices A³ and A4, respectively.

The graph 19 has perfect 3-colorings with the matrices A³ and A4. Consider two mappings T¹ and T² as follows:

\[T_1(a_2) = T_1(a_9) = 1, T_1(a_1) = T_1(a_4) = T_1(a_6) = T_1(a_8) = 2,\] \(T_1(a_3) = T_1(a_5) = T_1(a_7) = T_1(a_9) = 3.\) \(T_2(a_1) = 1, T_2(a_3) = T_2(a_6) = 2 = T_2(a_9) = 2,\) \(T_2(a_2) = T_2(a_4) = T_2(a_5) = T_2(a_7) = T_2(a_8) = T_2(a_{10}) = 3.\)

It is clear that T¹ and T² are perfect 3-coloring with the matrices A³ and A4, respectively. There are no perfect 3-colorings with the matrices A² and A⁴ for graph 1.

Contrary to our claim, suppose that T is a perfect 3-coloring with the matrix A² for graph 1. According to the matrix A2, each vertex with white color has a neighbor with white color, so the two vertices with white color are adjacent. In the case that a¹ ↔ a2, a¹ ↔ a3, a² ↔ a4, a³ ↔ a⁴ by symmetry a⁷ ↔ a8, a⁷ ↔ a9, a⁸ ↔ a¹⁰ and a⁹ ↔ a10, they have less than four adjacent vertices. These vertices are red color, which is a contradiction. So a⁵ ↔ a6, a⁴ ↔ a⁵ and its symmetric a⁶ ↔ a⁷ will be remain that are white color. In the case that a⁴ ↔ a5, the neighbors of a⁴ and a⁵ are red color and vertex a¹ that is their neighbor's is also red color has two neighbors with red color which it is not possible. If a⁵ and a⁶ are white color, adjacent vertices are red color and other vertices are black color, so each black color is adjacent to another black color vertex, which is a contradiction. So we conclude the graph 1 has no perfect 3-coloring with matrix A2.

Contrary to our claim, suppose that T is a perfect 3-coloring with the matrix A⁴ for graph 1. According to the matrix A4, each vertex with white color has three adjacent with black color. If a¹ is white color, then a2, a3, a⁵ are black color, which is a contradiction with the second row of matrix A4. If a² is white color, then according to the matrix A4, the vertices a1, a3, a⁴ are black color, which is a contradiction with the second row of matrix A4. If a³ is white color, then according to the matrix A4, the vertices a1, a2, a⁴ are black color, which is a contradiction with the second row of matrix A4. If a⁴ is white color, then according to the matrix A4, the vertices a2, a3, a⁵ are black color, which is a contradiction with the second row of matrix A4. If a⁵ is white color, then a³ is a vertex that is black color and has three red color neighbors, which is a counteraction with the second row of matrix A4. According to the symmetric, the vertices a6, a7, a8, a9, a¹⁰ can not be white color. Therefore the graph 1 has no perfect 3-coloring with matrix A4.

As it is stated in the before paragraphs, the graph 1 has no perfect 3-coloring with matrices A² and A4.

About other graphs in Figure 1, similarly, we can get the same result as in Table 1.

References

• [1] M. Alaeiyan and A. Abedi, Perfect 2-colorings of Johnson graphs J(4, 3), J(4, 3), J(6, 3) and Petersen graph, Ars Combinatoria, (to appear).
• [2] M. Alaeiyan and H. Karami, Perfect 2-colorings of the generalized Petersen graph, Proceedings Mathematical Sciences 126 (2016), 1–6.
• [3] S.V. Avgustinovich and I. Yu. Mogilnykh, Perfect 2-colorings of Johnson graphs J(6, 3) and J(7, 3), Lecture Notes in Computer Science 5228 (2008), 11–19.
• [4] S.V. Avgustinovich and I. Yu. Mogilnykh, Perfect colorings of the Johnson graphs J(8, 3) and J(8, 4) with two colors, Journal of Applied and Industrial Mathematics 5 (2011), 19-30.
• [5] F.C. Bussemaker, S. Cobeljic, D.M. Cvetkovic and J.J. Seidel, Computer invetigation of cubic graphs, Technische Hpgesschool Eindhoven Nederland Onderafedeling Der Wiskunde, January 1976.

• [6] D.G. Fon-Der-Flaass, A bound on correlation immunity, Siberian Electronic Mathematical Reports Journal 4 (2007), 133–135.
• [7] D.G. Fon-Der-Flaass, Perfect 2-colorings of a hypercube, Siberian Mathematical Journal 4 (2007), 923–930.
• [8] D.G. Fon-der-Flaass, Perfect 2-colorings of a 12-dimensional Cube that achieve a bound of correlation immunity, Siberian Mathematical Journal 4 (2007), 292–295.
• [9] A.L. Gavrilyuk and S.V. Goryainov, On perfect 2-colorings of Johnson graphs J(v, 3), Journal of Combinatorial Designs 21 (2013), 232–252.
• [10] C. Godsil, Compact graphs and equitable partitions, Linear Algebra and Its Application 255 (1997), 259–266.
• [11] C. Godsil and R. Gordon, Algebraic graph theory, Springer Science+Business Media, LLC (2004).