Original Research Article

Article volume = 2021 and issue = 2

Pages: 136–142

Article publication Date: November, 1, 2021

You can download PDF file of the article here: Download

Visited 35 times and downloaded 13 times

Perfect 3-Colorings of Some Generalized Peterson Graph

Mehdi Alaeiyan, Zahra Shokoohi

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


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 3-colorings of some the generalized peterson graph.


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

  • [1] M. Alaeiyan and A. Mehrabani, Perfect 3-colorings of cubic graphs of order 10 , Electronic Journal of Graph Theory andApplications (EJGTA),5(2) (2017),PP.194-206. 2.2, 2.4
  • [2] M. Alaiyan, A. Mehrabani, Perfect 3- colorings of the platonic graph, Iranian J. Sci. Technol., Trans. A Sci. (2017) 1-9. 2.3
  • [3] 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
  • [4] 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
  • [5] D.G. Fon-Der-Flaass, A bound on correlation immunity, Siberian Electronic Mathematical Reports Journal 4 (2007), 133-135. 1
  • [6] D.G. Fon-Der-Flaass, Perfect 2-colorings of a hypercube, Siberian Mathematical Journal 4(2007), 923-930. 1
  • [7] 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
  • [8] 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
  • [9] 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 3-Colorings of Some Generalized Peterson Graph, Communications in Combinatorics, Cryptography & Computer Science, 2021(2), PP.136–142, 2021
  • Export citation to BibTeX