|
Эта публикация цитируется в 5 научных статьях (всего в 5 статьях)
Дискретная математика и математическая кибернетика
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
Аннотация:
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.
Ключевые слова:
perfect coloring, circulant graph, Cayley graph, equitable partition.
Поступила 2 февраля 2020 г., опубликована 17 апреля 2020 г.
Образец цитирования:
O. G. Parshina, M. A. Lisitsyna, “The perfect $2$-colorings of infinite circulant graphs with a continuous set of odd distances”, Сиб. электрон. матем. изв., 17 (2020), 590–603
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/semr1233 https://www.mathnet.ru/rus/semr/v17/p590
|
Статистика просмотров: |
Страница аннотации: | 242 | PDF полного текста: | 103 | Список литературы: | 23 |
|