|
|
|
Perfect 3-colorings on 6-regular graphs of order 9 |
Ziqiu LIU, Yunfeng ZHAO( ), Yuqin ZHANG |
| School of Mathematics, Tianjin University, Tianjin 300350, China |
|
|
|
|
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 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.
|
| Keywords
Perfect coloring
equitable partition
regular graph
|
|
Corresponding Author(s):
Yunfeng ZHAO
|
|
Issue Date: 10 July 2019
|
|
| 1 |
M Aleiyan, A Mehrabani. Perfect 3-colorings of the cubic graphs of order 10. Electron J Graph Theory Appl (EJGTA), 2017, 5(2): 194–206
https://doi.org/10.5614/ejgta.2017.5.2.3
|
| 2 |
S Avgustinovich, I Mogilnykh. 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
https://doi.org/10.1007/978-3-540-87448-5_2
|
| 3 |
S Avgustinovich, I Mogilnykh. Perfect colorings of the Johnson graphs J(8, 3) and J(8, 4) with two colors. J Appl Ind Math, 2011, 5: 19–30
https://doi.org/10.1134/S1990478911010030
|
| 4 |
P Delsarte. An algebraic approach to the association schemes of coding theory. Philips Res Rep Suppl, 1973, 10: 1–97
|
| 5 |
D G Fon-Der-Flaass. A bound on correlation immunity. Sib Elektron Mat Izv, 2007, 4: 133–135
|
| 6 |
D G Fon-Der-Flaass. Perfect 2-colorings of a 12-dimensional Cube that achieve a bound of correlation immunity. Sib Math J, 2007, 4: 292–295
https://doi.org/10.1007/s11202-007-0075-4
|
| 7 |
D G Fon-Der-Flaass. Perfect 2-colorings of a hypercube. Sib Math J, 2007, 4: 923–930
https://doi.org/10.1007/s11202-007-0075-4
|
| 8 |
A L Gavrilyuk, S V Goryainov. On perfect 2-colorings of Johnson graphs J(v, 3). J Combin Des, 2013, 21: 232–252
https://doi.org/10.1002/jcd.21327
|
| 9 |
C Godsil. Compact graphs and equitable partitions, Linear Algebra Appl, 1997, 255: 259–266
https://doi.org/10.1016/S0024-3795(97)83595-1
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|