Please wait a minute...
Frontiers of Mathematics in China

ISSN 1673-3452

ISSN 1673-3576(Online)

CN 11-5739/O1

Postal Subscription Code 80-964

2018 Impact Factor: 0.565

Front. Math. China    2019, Vol. 14 Issue (3) : 605-618    https://doi.org/10.1007/s11464-019-0768-6
RESEARCH ARTICLE
Perfect 3-colorings on 6-regular graphs of order 9
Ziqiu LIU, Yunfeng ZHAO(), Yuqin ZHANG
School of Mathematics, Tianjin University, Tianjin 300350, China
 Download: PDF(275 KB)  
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
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 A1,A2,...,An such that for all i,j{1,2,...,n}, each vertex of Ai is adjacent to aij vertices of Aj. The matrix A=(aij)n×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.

Keywords Perfect coloring      equitable partition      regular graph     
Corresponding Author(s): Yunfeng ZHAO   
Issue Date: 10 July 2019
 Cite this article:   
Ziqiu LIU,Yunfeng ZHAO,Yuqin ZHANG. Perfect 3-colorings on 6-regular graphs of order 9[J]. Front. Math. China, 2019, 14(3): 605-618.
 URL:  
https://academic.hep.com.cn/fmc/EN/10.1007/s11464-019-0768-6
https://academic.hep.com.cn/fmc/EN/Y2019/V14/I3/605
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