|
This article is cited in 5 scientific papers (total in 5 papers)
Discrete mathematics and mathematical cybernetics
The perfect $2$-colorings of infinite circulant graphs with a continuous set of odd distances
O. G. Parshinaa, M. A. Lisitsynab a Czech Technical University in Prague, 13, Trojanova, Prague, 120 00, Czech Republic
b Marshal Budyonny Military Academy of Telecommunications, 3, Tikhoretskii ave., St. Petersburg, 194064, Russia
Abstract:
A vertex coloring of a given simple graph $G=(V,E)$ with $k$ colors ($k$-coloring) is a map from its vertex set to the set of integers $\{1,2,3,\dots, k\}$. A coloring is called perfect if the multiset of colors appearing on the neighbours of any vertex depends only on the color of the vertex. We consider perfect colorings of Cayley graphs of the additive group of integers with generating set $\{1,-1,3,-3,5,-5,\dots, 2n-1,1-2n\}$ for a positive integer $n$. We enumerate perfect $2$-colorings of the graphs under consideration and state the conjecture generalizing the main result to an arbitrary number of colors.
Keywords:
perfect coloring, circulant graph, Cayley graph, equitable partition.
Received February 2, 2020, published April 17, 2020
Citation:
O. G. Parshina, M. A. Lisitsyna, “The perfect $2$-colorings of infinite circulant graphs with a continuous set of odd distances”, Sib. Èlektron. Mat. Izv., 17 (2020), 590–603
Linking options:
https://www.mathnet.ru/eng/semr1233 https://www.mathnet.ru/eng/semr/v17/p590
|
Statistics & downloads: |
Abstract page: | 220 | Full-text PDF : | 96 | References: | 10 |
|