RESEARCH ARTICLE

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

  • Ziqiu LIU ,
  • Yunfeng ZHAO ,
  • Yuqin ZHANG
Expand
  • School of Mathematics, Tianjin University, Tianjin 300350, China

Received date: 06 Apr 2019

Accepted date: 21 Apr 2019

Published date: 15 Jun 2019

Copyright

2019 Higher Education Press and Springer-Verlag GmbH Germany, part of Springer Nature

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.

Cite this article

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

Outlines

/