|
This article is cited in 6 scientific papers (total in 6 papers)
Perfect colorings of the infinite circulant graph with distances 1 and 2
M. A. Lisitsynaa, O. G. Parshinabc a Marshal Budyonny Military Academy of Telecommunications,
3 Tikhoretsky Ave., 194064 St. Petersburg, Russia
b Sobolev Institute of Mathematics,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
c Institut Camille Jordan, Université Claude Bernard Lyon 1, 43 Boulevard du 11 Novembre 1918, F-69622 Villeurbanne Cedex, France
Abstract:
A coloring of the vertex set in a graph is called perfect if all its identically colored vertices have identical multisets of colors of their neighbors. Refer as the infinite circulant graph with continuous set of $n$ distances to the Cayley graph of the group $\mathbb{Z}$ with generator set $\{1,2,\ldots,n\}$. We obtain a description of all perfect colorings with an arbitrary number of colors of this graph with distances $1$ and $2$. In 2015, there was made a conjecture characterizing perfect colorings for the infinite circulant graphs with a continuous set of $n$ distances. The obtained result confirms the conjecture for $n = 2$. The problem is still open in the case of $n > 2$. Bibliogr. 12.
Keywords:
perfect coloring, circulant graph, equitable partition.
Received: 02.12.2016 Revised: 30.03.2017
Citation:
M. A. Lisitsyna, O. G. Parshina, “Perfect colorings of the infinite circulant graph with distances 1 and 2”, Diskretn. Anal. Issled. Oper., 24:3 (2017), 20–34; J. Appl. Industr. Math., 11:3 (2017), 381–388
Linking options:
https://www.mathnet.ru/eng/da873 https://www.mathnet.ru/eng/da/v24/i3/p20
|
Statistics & downloads: |
Abstract page: | 244 | Full-text PDF : | 177 | References: | 37 | First page: | 5 |
|