Investigating 1-perfect code using Dominating set

Document Type : Research Paper


1 Faculty of Mathematics, Statistics, and Computer Science, Semnan University, Semnan, Iran

2 Faculty of Mathematics, Statistics and Computer Science, Semnan University, Semnan, Iran


In this article, we investigate the relation between dominating sets and 1-perfect codes. We also study perfect colorings of some Johnson graphs in two colors using linear programming problem.


[1] S. V. Avgustinovich and I. Yu.Mogil’nykh, Perfect colorings of the Johnson graphs J(8, 3) and J(8, 4) with two colors, J. Appl. Ind. Math. 5(1) (2011) 19–30.
[2] S. V. Avgustinovich and M. A. Lisitsyna, Perfect 2-Colorings of Transitive Cubic Graphs, J. Appl. Ind. Math. (2011) 519-528.
[3] N. Biggs, Algebraic Graph Theory, Cambridge University Press, England, 1974.
[4] D. B. Khoroshilova, On circular perfect colorings with two colors, Diskret. Anal. Issled. Oper. 16 (2009) 80–92.
[5] I. Yu. Mogilnykh and S. V. Avgustinovich, Perfect 2-Colorings of Johnson Graphs J(6, 3) and J(7, 4) , Lecture Notes in Computer Science, Vol. 5228, Springer, Berlin, 2008.
[6] K. V. Vorob’ev and D. G. Fon-der-Flaass, On perfect 2-colorings of a hypercube, Siberian Elect.. Mat. Izv. 7 (2010) 65–75.
[7] D. B. West, Introduction to Graph Theory, University of Illinois – Urbana, 2002.
Volume 12, Issue 2
November 2021
Pages 479-483
  • Receive Date: 10 July 2019
  • Accept Date: 24 September 2019