Том 18, номер 6, 2011 г., Стр. 82-89

УДК 519.8
Хорошилова Д. Б.
О параметрах совершенных 2-раскрасок циркулянтных графов

Аннотация:
Предлагается конструкция, позволяющая строить совершенные 2-раскраски циркулянтных графов с новыми неизвестными ранее параметрами.
Библиогр. 18.

Ключевые слова: совершенная раскраска, циркулянтный граф, сплошная раскраска.

Хорошилова Дарья Борисовна ¹
1. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: dkhor@ngs.ru

Статья поступила 13 мая 2011 г.
Исправленный вариант — 23 августа 2011 г.

Литература

[1] Августинович С. В., Бородин О. В., Фрид А. Э. Дистрибутивные раскраски плоских триангуляций минимальной степени 5 // Дискрет. анализ и исслед. операций. Сер. 1. — 2001. — Т. 8, № 3. — С. 3–16.

[2] Визинг В. Г. Дистрибутивная раскраска вершин графа // Дискрет. анализ и исслед. операций. — 1995. — Т. 2, № 4. — С. 3–12.

[3] Ефремова Е. М., Молодых Е. А. Параметры совершенных раскрасок бесконечной кубической решётки в два цвета // Устное сообщение.

[4] Прасолов В. В. Задачи и теоремы линейной алгебры. — М: Наука, Физматлит, 1996. — 304 с.

[5] Прасолов В. В. Многочлены. — М: МЦНМО, 2001. — С. 104–113.

[6] Пузынина С. А. Периодичность совершенных раскрасок бесконечной прямоугольной решётки // Дискрет. анализ и исслед. операций. Сер. 1. — 2004. — Т. 11, № 1. — С. 79–92.

[7] Пузынина С. А. Совершенные раскраски вершин графа $G(\mathbb {Z}^2)$ в три цвета // Дискрет. анализ и исслед. операций. Сер. 2. — 2005. — Т. 12, № 1. — С. 37–54.

[8] Фон-Дер-Флаасс Д. Г. Совершенные 2-раскраски 12-мерного куба, достигающие границы корреляционной иммунности // Сиб. электрон. мат. изв. — 2007. — Т. 4. — С. 292–295.

[9] Фон-Дер-Флаасс Д. Г. Совершенные 2-раскраски гиперкуба // Сиб. мат. журн. — 2007. — Т. 48, № 4. — С. 924–931.

[10] Харари Ф. Теория графов. — М: КомКнига, 2006. — 296 с.

[11] Хорошилова Д. Б. О циркулярных совершенных раскрасках в два цвета // Дискрет. анализ и исслед. операций. — 2009. — Т. 16, № 1. — С. 80–92.

[12] Цветкович Д., Дуб М., Захс Х. Спектры графов. Теория и применение. — Киев: Наукова думка, 1984. — 384 с.

[13] Axenovich M. A. On multiple coverings of the infinite rectangular grid with balls of constant radius // Discrete Math. — 2003. — Vol. 268, N 1–3. — P. 31–49.

[14] Agustini E., Costa S. I. R., Muniz M., Palazzo R. Graphs, tesselations, and perfect codes on flat tori // IEEE Trans. Inf. Theory. — 2004. — Vol. 50, N 10. — P. 2363–2377.

[15] Dorbec P., Gravier S., Honkala I., Mollard M. Weighted codes in Lee metrics // Des. Codes Cryptography. — 2009. — Vol. 52. — P. 209–218.

[16] Dorbec P., Gravier S., Honkala I., Mollard M. Weighted perfect codes in Lee metric // Electron. Notes Discrete Math. — 2009. — Vol. 34. — P. 477–481.

[17] Godsil C. Equitable partitions // Combinatorics. Paul Erdös is eighty. Vol. 1. — Budapest, Hungary: Janos Bolyai Mathematical Society, 1993. — P. 173—192.

[18] Krotov D. S. Perfect colorings of $\mathbb {Z}^2$: nine colors // http://arxiv.org/abs/0901.0004. — 2008. — 177 p.