Perfect 3-colorings on 6-regular graphs of order 9

Abstract

The concept of a perfect coloring, introduced by P. Delsarte, generalizes the concept of completely regular code. We study the perfect 3-colorings (also known as the equitable partitions into three parts) on 6-regular graphs of order 9. A perfect n-colorings of a graph is a partition of its vertex set. It splits vertices into n parts {{\displaystyle A}}_{\mathrm{1}},{{\displaystyle A}}_{\mathrm{2}},\mathrm{...},{{\displaystyle A}}_n such that for all i,j\in \{\mathrm{1},\mathrm{2},\mathrm{...},n\}, each vertex of A_i is adjacent to a_ij vertices of A_j. The matrix A={{\displaystyle ({{\displaystyle a}}_{ij})}}_{n\times n} is called quotient matrix or parameter matrix. In this article, we start by giving an algorithm to find all different types of 6-regular graphs of order 9. Then, we classify all the realizable parameter matrices of perfect 3-colorings on 6-regular graphs of order 9.

Key words： Perfect coloring; equitable partition; regular graph

References

1 Aleiyan M, Mehrabani A. Perfect 3-colorings of the cubic graphs of order 10. Electron J Graph Theory Appl (EJGTA), 2017, 5(2): 194–206

2 Avgustinovich S, Mogilnykh I. Perfect 2-colorings of Johnson graphs J(6, 3) and J(7, 3). In: Barbero A, ed. Coding Theory and Applications. Lecture Notes in Comput Sci, Vol 5228. Berlin: Springer, 2008, 11–19

3 Avgustinovich S, Mogilnykh I. Perfect colorings of the Johnson graphs J(8, 3) and J(8, 4) with two colors. J Appl Ind Math, 2011, 5: 19–30

4 Delsarte P. An algebraic approach to the association schemes of coding theory. Philips Res Rep Suppl, 1973, 10: 1–97

5 Fon-Der-Flaass D G. A bound on correlation immunity. Sib Elektron Mat Izv, 2007, 4: 133–135

6 Fon-Der-Flaass D G. Perfect 2-colorings of a 12-dimensional Cube that achieve a bound of correlation immunity. Sib Math J, 2007, 4: 292–295

7 Fon-Der-Flaass D G. Perfect 2-colorings of a hypercube. Sib Math J, 2007, 4: 923–930

8 Gavrilyuk A L, Goryainov S V. On perfect 2-colorings of Johnson graphs J(v, 3). J Combin Des, 2013, 21: 232–252

9 Godsil C. Compact graphs and equitable partitions, Linear Algebra Appl, 1997, 255: 259–266