Frontiers of Mathematics in China >
Perfect 3-colorings on 6-regular graphs of order 9
Received date: 06 Apr 2019
Accepted date: 21 Apr 2019
Published date: 15 Jun 2019
Copyright
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 such that for all , each vertex of Ai is adjacent to aij vertices of Aj. The matrix 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
Ziqiu LIU , Yunfeng ZHAO , Yuqin ZHANG . Perfect 3-colorings on 6-regular graphs of order 9[J]. Frontiers of Mathematics in China, 2019 , 14(3) : 605 -618 . DOI: 10.1007/s11464-019-0768-6
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
|
/
〈 | 〉 |