![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
Abstract
Perfect coloring is a generalization of the notion of completely regular codes, given by Delsarte. A perfect -coloring of a graph
with
colors is a partition of the vertex set of
into m parts
, . . . ,
such that, for all
, every vertex of
is adjacent to the same number of vertices, namely,
vertices, of
. The matrix
, is called the parameter matrix. We study the perfect 2-colorings (also known as the equitable partitions into two parts) of the cubic graphs of order less than or equal to 10. In particular, we classify all the realizable parameter matrices of perfect 2-colorings for the cubic graphs of order less than or equal to 10.
1 Introduction
The concept of a perfect -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 [Citation1]).
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 perfect codes in Johnson graphs. Therefore, some effort has been done on enumerating the parameter matrices of some Johnson graphs, including ,
,
,
, and
(
odd) (see [Citation2–4]).
Fon-Der-Flass enumerated the parameter matrices of -dimensional cube for
. He also obtained some constructions and a necessary condition for the existence of perfect 2-colorings of the
-dimensional cube with a given parameter matrix (see [Citation5–7]). In [Citation8–11] perfect 2-colorings and perfect 3-colorings of some graphs were described. So for cubic graphs of order less than or equal to 10, the problem of existence of perfect 2-colorings was open. In this article, we enumerate the parameter matrices of all perfect 2-colorings of the cubic graphs of order less than or equal to
.
2 Preliminaries
Definition 2.1
For each graph and each integer
, a mapping
is called a perfect
-coloring with matrix
, if it is surjective, and for all
, for every vertex of color
, the number of its neighbors of color
is equal to
. The matrix
is called the parameter matrix of a perfect coloring. When
, we denote the two colors by W and B representing white and black respectively.
A cubic graph is a 3-regular graph. Cubic graphs of order less than or equal to 10 are given in . Wherever possible the vertices of the graph are labeled with B or W giving a perfect 2-coloring.
Now, we first give some results concerning necessary conditions for the existence of perfect 2-colorings of a -regular graph with a given parameter matrix
.
The simplest condition for the existence of a perfect 2-colorings of a -regular graph with the matrix
is:
If
is connected, then
and
are both non-zero. By the given conditions, we can see that a parameter matrix of a perfect 2-coloring of cubic graphs must be one of the following matrices:
The next proposition gives a formula for calculating the number of white vertices in a perfect 2-coloring.
Proposition 2.2
[Citation2] If is the set of white vertices in a perfect 2-coloring of a graph
with matrix
, then
The number is called an eigenvalue of a graph
, if
is an eigenvalue of the adjacency matrix of this graph. The number
is called an eigenvalue of a perfect coloring
into m colors with the matrix
, if
is an eigenvalue of
. The next theorem demonstrates the connection between the introduced notions.
Theorem 2.3
[Citation12] If is a perfect coloring of a graph
in
colors, then any eigenvalue of
is an eigenvalue of
.
Corollary 2.4
Every perfect 2-coloring of a -regular graph with parameter matrix
has two eigenvalues: one is
, and the other is
such that we obviously have
. So, from Theorem 2.3 , we conclude that
is an eigenvalue of a
-regular connected graph which is not equal to
.
3 Main results
In this section, we enumerate the parameter matrices of all perfect 2-colorings of the cubic connected graphs of order less than or equal to 10. Any cubic graph of order is isomorphic to
and for the perfect 2-coloring of this graph given in , the parameter matrix is
. Also, it follows from Proposition 2.2 that the matrices
and
cannot be parameter matrices. In the next theorems, we introduce the parameter matrices for cubic graphs of order
,
, and
.
Theorem 3.1
The graph has no perfect 2-coloring with parameter matrix
.
Proof
Suppose there exists a perfect 2-coloring of
with matrix
. Then each vertex with color 1 has one adjacent vertex with color 2. We now have two possibilities:
(1) and
.
(2) and
.
In both cases we get , which is a contradiction with the second row of
. Hence
has no perfect 2-coloring with matrix
.
Theorem 3.2
The graph has no perfect 2-coloring with parameter matrix
.
Proof
The proof is similar to the proof of Theorem 3.1.
Theorem 3.3
The graph has perfect 2-coloring with parameter matrices
and graph
has perfect 2-coloring with parameter
.
Proof
For the perfect coloring of and
given in , the corresponding parameter matrices are
and
respectively. Also the mapping defined by
and
gives a perfect 2-coloring of
with matrix
.
Theorem 3.4
The graph has no perfect 2-coloring with parameter matrix
.
Proof
Suppose there exists a perfect 2-coloring of
with matrix
. Then each vertex with color 1 has two adjacent vertices with color 1. We now have three possibilities:
(1) and
.
(2) and
.
(3) and
.
In case 1 we get , which is a contradiction with the second row of matrix
. In other both cases we get a contradiction with the second row of
. Hence
has no perfect 2-coloring with matrix
.
Theorem 3.5
The graph has no perfect 2-coloring with parameter matrices
and
.
Proof
The proof is similar to the proof of Theorem 3.4.
Theorem 3.6
The graph has no perfect 2-coloring with parameter matrix
.
Proof
The proof is similar to the proof of Theorem 3.4.
Theorem 3.7
The Graphs ,
,
and
of order
have perfect 2-colorings.
Proof
For the perfect coloring of and
given in , the corresponding parameter matrices are
and
respectively. Also the mapping defined by:
gives a perfect 2-coloring of
with matrix
, the mappings defined by:
gives a perfect 2-colorings of
with matrices
,
and
, respectively and the mappings defined by:
gives a perfect 2-coloring of
with matrix
.
Theorem 3.8
The parameter matrices of cubic graphs of order are listed in .
Table 1 The parameter matrices of cubic graphs of order 10.
Proof
As it has been shown in the previous section, only matrices ,
, …,
can be parameter matrices. With consideration the eigenvalues of cubic graphs, and using Proposition 2.2 and Theorem 2.3, it can be seen that the connected cubic graphs with 10 vertices can have perfect
-coloring with matrices
,
,
and
which is represented by . For the perfect coloring of graphs
and graphs
given in , the corresponding parameter matrices are
and
respectively. Also the mapping defined by:
gives a perfect 2-coloring of graph
with matrix
and the mapping defined by:
gives a perfect 2-coloring of graph
with matrix
.
There are no perfect 2-colorings with the matrices for graph
. Suppose there exists a perfect 2-coloring
of
with matrix
. Then each vertex with color 1 has two adjacent vertices with color 1. We now have three possibilities:
(1) and
.
(2) and
.
(3) and
.
In all three cases, the vertex by color 2 has two adjacent vertex with color 1, which is a contradiction with the second row of . Hence graph
has no perfect 2-coloring with matrix
.
About other graphs in , similarly, we can get the same result as in .
Table 2 The possibility of existence a perfect 2-coloring to cubic graphs of order 10.
References
- GodsilC., Compact graphs and equitable partitions Linear Algebra and Its Application, Vol. 2551997 259–266
- AvgustinovichS.V.MogilnykhI. Yu., Perfect 2-colorings of Johnson graphs J(6, 3) and J(7, 3) Lecture Notes in Comput. Sci. 52282008 11–19
- AvgustinovichS.V.MogilnykhI.Yu., Perfect colorings of the Johnson graphs J(8, 3) and J(8, 4) with two colors J. Appl. Ind. Math. 52011 19–30
- GavrilyukA.L.GoryainovS.V., On perfect 2-colorings of Johnson graphs J(v,3) J. Combin. Des. 212013 232–252
- Fon-Der-FlaassD.G., A bound on correlation immunity Siberian Electron. Math. Rep. J. 42007 133–135
- Fon-Der-FlaassD.G., Perfect 2-colorings of a hypercube Sib. Math. J. 42007 923–930
- Fon-der FlaassD.G., Perfect 2-colorings of a 12-dimensional Cube that achieve a bound of correlation immunity Sib. Math. J. 42007 292–295
- AlaeiyanM.MehrabaniA., Perfect 3-colorings of the cubic graphs of order 10 Electron. J. Graph Theory Appl. 5 2 2017 194–206
- AlaiyanM.MehrabaniA., Perfect 3-colorings of the platonic graph Iranian J. Sci. Technol., Trans. A Sci.2017 1-9
- AlaeiyanM.KaramiH., Perfect 2-colorings of the generalized Petersen graph Proc. Math. Sci. 1262016 1–6
- AlaiyanM.MehrabaniA., Perfect 3-colorings of cubic graphs of order 8 Armenian J. Math. 10 2 2018 1–11
- BussemakerF.C.CobeljicS.CvetkovicD.M.SeidelJ.J., Computer investigation of cubic graphs Tech. Hogeschool Eindhoven Ned. Onderafedeling Wisk.1976