Original Research Article

Article volume = 2021 and issue = 2

Pages: 143–151

Article publication Date: November, 1, 2021

You can download PDF file of the article here: Download

Visited 211 times and downloaded 79 times

Perfect 4-Colorings of Some Generalized Peterson Graph

Mehdi Alaeiyan, Zahra Shokoohi

School of Mathematics, Iran University of Science and Technology, Narmak, Tehran 16846, Iran.

Abstract:

The notion of a perfect coloring, introduced by Delsarte, generalizes the concept of completely regular code. A perfect z-colorings of a graph is a partition of its vertex set. It splits vertices into z parts P1, , Pz such that for all i, j 2 f1, , zg, each vertex of Pi is adjacent to pij, vertices of Pj. The matrix P = (pij)i,j2f1, ,zg, is called parameter matrix. In this article, we classify all the realizable parameter matrices of perfect 4-colorings of some the generalized peterson graph.

Keywords:

Parameter matrices, Perfect coloring, Equitable partition, Generalized peterson graph.

References:
  • [1] M. Alaeiyan, Z. Vahedi, M. Maghasedi, Perfect 4-colorings of the 3-regular graphs of order at most 8, Journal of mathematical extention (2021), 1-16. 2.2
  • [2] S.V. Avgustinovich and I. Yu. Mogilnykh, Perfect 2-colorings of Johnson graphs J(6, 3) and J(7, 3), Lecture Notes in Computer Science 5228 (2008), 11-19. 1
  • [3] S.V. Avgustinovich and I. Yu. Mogilnykh, Perfect colorings of the Johnson graphs J(8, 3) and J(8, 4) with two colors, Journal of Applied and Industrial Mathematics 5 (2011), 19-30. 1
  • [4] D.G. Fon-Der-Flaass, A bound on correlation immunity, Siberian Electronic Mathematical Reports Journal 4 (2007), 133-135. 1
  • [5] D.G. Fon-Der-Flaass, Perfect 2-colorings of a hypercube, Siberian Mathematical Journal 4(2007), 923-930. 1
  • [6] D.G. Fon-der-Flaass, Perfect 2-colorings of a 12-dimensional Cube that achieve a bound of correlation immunity, Siberian Mathematical Journal 4 (2007), 292-295. 1
  • [7] A.L. Gavrilyuk and S.V. Goryainov, On perfect 2-colorings of Johnson graphs J(v, 3), Journal of Combinatorial Designs 21 (2013), 232-252. 1
  • [8] C. Godsil, Compact graphs and equitable partitions, Linear Algebra and Its Application 255(1997), 259-266. 1, 2.1
Cite this article as:
  • Mehdi Alaeiyan, Zahra Shokoohi, Perfect 4-Colorings of Some Generalized Peterson Graph, Communications in Combinatorics, Cryptography & Computer Science, 2021(2), PP.143–151, 2021
  • Export citation to BibTeX