Циркулярный график

Граф Пейли 13-го порядка, пример циркулянтного графа.

В теории графов циркулянтный граф — это неориентированный граф, на который действует циклическая группа симметрий , которая переводит любую вершину в любую другую вершину . Иногда его называют циклическим графом , ^[1], но этот термин имеет и другие значения.

Эквивалентные определения

Циркулярные графы можно описать несколькими эквивалентными способами: ^[2]

Группа автоморфизмов графа включает циклическую подгруппу , которая действует транзитивно на вершинах графа. Другими словами, граф имеет автоморфизм , который является циклической перестановкой его вершин.
Граф имеет матрицу смежности , которая является циркулянтной матрицей .
N вершин графа можно пронумеровать от 0 до $n$ $- 1$ таким образом, что если некоторые две вершины с номерами $x$ $и$ ( $x$ $+$ $d$ $)$ $mod$ $n$ являются смежными, то любые две вершины с номерами $z$ и $($ $z$ $+$ $d$ $) mod$ $n$ являются смежными.
Граф можно нарисовать (возможно, с пересечениями) так, чтобы его вершины лежали в углах правильного многоугольника , и каждая вращательная симметрия многоугольника также является симметрией рисунка.
Граф представляет собой граф Кэли циклической группы . ^[3]

Примеры

Каждый граф-цикл является циркулянтным графом, как и каждый граф-корона с числом вершин, сравнимым с 2 по модулю 4.

Графы Пейли порядка $n$ (где $n$ — простое число, сравнимое с 1 по модулю 4 ) — это граф, в котором вершинами являются числа от 0 до $n - 1$ , а две вершины являются смежными, если их разность является квадратичным вычетом по модулю $n$ . Поскольку наличие или отсутствие ребра зависит только от разности по модулю $n$ двух чисел вершин, любой граф Пейли является циркулянтным графом.

Каждая лестница Мёбиуса является циркулянтным графом, как и каждый полный граф . Полный двудольный граф является циркулянтным графом, если он имеет одинаковое количество вершин по обе стороны от своей двудольности.

Если два числа $m$ и $n$ взаимно просты , то граф ладьи $m \times n$ (граф, имеющий вершину для каждой клетки шахматной доски $m$ $\times$ $n$ и ребро для каждых двух клеток, между которыми ладья может переместиться за один ход) является циркулянтным графом. Это происходит потому, что его симметрии включают в себя в качестве подгруппы циклическую группу C _mn C _m × C _n . В более общем случае, в этом случае тензорное произведение графов между любыми циркулянтами $m$ - и $n$ -вершинными является само по себе циркулянтом. ^[2] $\симеq$

Многие из известных нижних границ чисел Рамсея получены из примеров циркулянтных графов, которые имеют небольшие максимальные клики и небольшие максимальные независимые множества . ^[1]

Конкретный пример

Циркулянтный граф со скачками определяется как граф с узлами, помеченными как i , где каждый узел смежный с 2k узлами . $C_{n}^{s_{1},\ldots ,s_{k}}$ $s_{1},\ldots ,s_{k}$ $n$ $0,1,\ldots ,n-1$ $i\pm s_{1},\ldots ,i\pm s_{k}\mod n$

Граф связен тогда и только тогда, когда . $C_{n}^{s_{1},\ldots ,s_{k}}$ $\НОД(n,s_{1},\ldots ,s_{k})=1$
Если — фиксированные целые числа , то число остовных деревьев удовлетворяет рекуррентному соотношению порядка . $1\leq s_{1}<\cdots <s_{k}$ $t(C_{n}^{s_{1},\ldots ,s_{k}})=na_{n}^{2}$ $а_{н}$ $2^{s_{k}-1}$
- В частности, где — n - е число Фибоначчи . $t(C_{n}^{1,2})=nF_{n}^{2}$ $F_{n}$

Самодополняющие циркулянты

Самодополнительный граф — это граф, в котором замена каждого ребра на не-ребро и наоборот даёт изоморфный граф . Например, граф цикла с пятью вершинами является самодополнительным, а также циркулянтным графом. В более общем смысле каждый граф Пейли простого порядка является самодополнительным циркулянтным графом. ^[4] Хорст Сакс показал, что если число $n$ обладает свойством, что каждый простой множитель $n$ сравним с 1 по модулю 4 , то существует самодополнительный циркулянт с $n$ вершинами. Он предположил , что это условие также необходимо: никакие другие значения $n$ не допускают существования самодополнительного циркулянта. ^[2]^[4] Гипотеза была доказана примерно 40 лет спустя Вильфредом. ^[2]

Догадка Адама

Определим циркулянтную нумерацию циркулянтного графа как маркировку вершин графа числами от 0 до $n - 1$ таким образом, что если некоторые две вершины с номерами $x$ и $y$ являются смежными, то любые две вершины с номерами $z$ и $(z - x + y) mod n$ являются смежными. Эквивалентно, циркулянтная нумерация — это нумерация вершин, для которых матрица смежности графа является циркулянтной матрицей.

Пусть $a$ — целое число, взаимно простое с $n$ , и пусть $b$ — любое целое число. Тогда линейная функция , которая переводит число $x$ в $ax + b,$ преобразует циркулянтную нумерацию в другую циркулянтную нумерацию. Андраш Адам предположил, что эти линейные отображения являются единственными способами перенумерации циркулянтного графа, сохраняя при этом свойство циркулянта: то есть, если $G$ и $H$ — изоморфные циркулянтные графы с разными нумерациями, то существует линейное отображение, которое преобразует нумерацию для $G$ в нумерацию для $H$ . Однако теперь известно, что гипотеза Адама ложна. Контрпример дают графы $G$ и $H$ с 16 вершинами каждый; вершина $x$ в $G$ соединена с шестью соседями $x \pm 1$ , $x \pm 2$ и $x \pm 7$ по модулю 16, тогда как в $H$ шесть соседей — это $x \pm 2$ , $x \pm 3$ и $x \pm 5$ по модулю 16. Эти два графа изоморфны, но их изоморфизм не может быть реализован линейным отображением. ^[2]

Гипотеза Тоиды уточняет гипотезу Адама, рассматривая только специальный класс циркулянтных графов, в которых все разности между соседними вершинами графа взаимно просты с числом вершин. Согласно этой уточненной гипотезе, эти специальные циркулянтные графы должны обладать свойством, что все их симметрии происходят из симметрий базовой аддитивной группы чисел по модулю $n$ . Это было доказано двумя группами в 2001 и 2002 годах. ^[5]^[6]

Алгоритмические вопросы

Существует алгоритм распознавания циркулянтных графов за полиномиальное время , и проблема изоморфизма для циркулянтных графов может быть решена за полиномиальное время. ^[7]^[8]

Ссылки

^ ab Малые числа Рамсея, Станислав П. Радзишовский, Electronic J. Combinatorics , динамический обзор 1, обновлено в 2014 г.
^ abcde Вильфред, В. (2004), «О циркулянтных графах», в Балакришнан, Р.; Сетураман, Г.; Уилсон, Робин Дж. (ред.), Теория графов и ее приложения (Университет Анна, Ченнаи, 14–16 марта 2001 г.), Alpha Science, стр. 34–36.
^ Alspach, Brian (1997), «Изоморфизм и графы Кэли на абелевых группах», Graph symmetry (Монреаль, PQ, 1996), NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., т. 497, Дордрехт: Kluwer Acad. Publ., стр. 1–22, MR 1468786.
^ аб Сакс, Хорст (1962). «Дополнительный графен». Публикации Mathematicae Дебрецен . 9 : 270–288. МР 0151953..
^ Музычук, Михаил; Клин, Михаил; Пёшель, Рейнхард (2001), "Проблема изоморфизма для циркулянтных графов с помощью теории колец Шура", Коды и схемы ассоциаций (Пискатауэй, Нью-Джерси, 1999) , DIMACS Ser. Discrete Math. Theoret. Comput. Sci., т. 56, Провиденс, Род-Айленд: Американское математическое общество, стр. 241–264, MR 1816402
^ Добсон, Эдвард; Моррис, Джой (2002), «Гипотеза Тоиды верна», Электронный журнал комбинаторики , 9 (1): R35:1–R35:14, MR 1928787
^ Музычук, Михаил (2004). «Решение проблемы изоморфизма для циркулянтных графов». Proc. London Math. Soc . 88 : 1–41. doi :10.1112/s0024611503014412. MR 2018956.
^ Евдокимов, Сергей; Пономаренко, Илья (2004). «Распознавание и проверка изоморфизма циркулянтных графов за полиномиальное время». Санкт-Петербургский математический журнал . 15 : 813–835. doi : 10.1090/s1061-0022-04-00833-7 . MR 2044629.

Внешние ссылки

Вайсштейн, Эрик В. «Циркулянтный граф». MathWorld .