Perfect 3-colorings of the cubic graphs of order 10

Mehdi Alaeiyan (School of Mathematics, Iran University of Science and Technology, Narmak, Tehran 16846, Iran)
Ayoob Mehrabani (School of Mathematics, Iran University of Science and Technology, Narmak, Tehran 16846, Iran)

Electronic Journal of Graph Theory and Applications (EJGTA)
Vol 5, No 2 (2017): Electronic Journal of Graph Theory and Applications

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 A_1, A_2, ..., A_m such that, for all $ i,j \in \lbrace 1, ... , m \rbrace $, every vertex of A_i is adjacent to the same number of vertices, namely, a_{ij} vertices, of A_j. The matrix $A=(a_{ij})_{i,j\in \lbrace 1,... ,m\rbrace }$, 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.