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

Граф Пэли порядка 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$ и ребро для каждых двух клеток, между которыми шахматная ладья может перемещаться за одно move) представляет собой циркулянтный граф. Это связано с тем, что ее симметрии включают в качестве подгруппы циклическую группу C _mn $\simeq$ C _м × C _п . В более общем смысле, в этом случае тензорное произведение графов между любыми $m-$ и $n$ -вершинными циркулянтами само по себе является циркулянтом. ^[2]

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

Конкретный пример [ править ]

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

График $C_{n}^{s_{1},\ldots ,s_{k}}$ связно тогда и только тогда, когда $\gcd(n,s_{1},\ldots ,s_{k})=1$ .
Если $1\leq s_{1}<\cdots <s_{k}$ $1\leq s_{1}<\cdots <s_{k}$ являются фиксированными целыми числами, тогда количество остовных деревьев $t(C_{n}^{s_{1},\ldots ,s_{k}})=na_{n}^{2}$ $t(C_{n}^{s_{1},\ldots,s_{k}})=na_{n}^{2}$ где $a_{n}$ $a_{n}$ удовлетворяет рекуррентному отношению порядка $2^{s_{k}-1}$ $2^{s_{k}-1}$ .
- В частности, $t(C_{n}^{1,2})=nF_{n}^{2}$ где $F_{n}$ — 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]

Ссылки [ править ]

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

Внешние ссылки [ править ]

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

[ds1-1] Jump up to: ^а ^б Малые числа Рамсея , Станислав П. Радзишовский, Electronic J. Combinatorics , динамический обзор 1, обновлено в 2014 г.

[v04-2] Jump up to: ^а ^б ^с ^д ^и Вильфред В. (2004), «О циркулянтных графах», Балакришнан, Р.; Сетураман, Г.; Уилсон, Робин Дж. (ред.), Теория графов и ее приложения (Университет Анны, Ченнаи, 14–16 марта 2001 г.) , Alpha Science, стр. 34–36 .

[3] Олспах, Брайан (1997), «Изоморфизм и графы Кэли на абелевых группах», Симметрия графа (Монреаль, PQ, 1996) , NATO Adv. наук. Инст. Сер. С Математика. Физ. наук, том. 497, Дордрехт: Клювер Акад. Опубл., стр. 1–22, MR 1468786 .

[s62-4] Jump up to: ^а ^б Сакс, Хорст (1962). «О самодополняющих графах». Публикации Mathematicae Дебрецен . 9 :270-288. МР 0151953 . .

[5] Музычук Михаил; Клин, Михаил; Пёшель, Рейнхард (2001), «Проблема изоморфизма циркулянтных графов с помощью теории колец Шура», Коды и ассоциативные схемы (Пискатауэй, Нью-Джерси, 1999) , DIMACS Ser. Дискретная математика. Теория. Вычислить. наук, том. 56, Провиденс, Род-Айленд: Американское математическое общество, стр. 241–264, MR 1816402.

[6] Добсон, Эдвард; Моррис, Джой (2002), «Гипотеза Тойды верна» , Electronic Journal of Combinatorics , 9 (1): R35:1–R35:14, MR 1928787

[muz04-7] Музычук, Михаил (2004). «Решение проблемы изоморфизма циркулянтных графов». Учеб. Лондонская математика. Соц . 88 : 1–41. дои : 10.1112/s0024611503014412 . МР 2018956 .

[ep04-8] Евдокимов, Сергей; Пономаренко, Илья (2004). «Распознавание и проверка изоморфизма циркулянтных графов за полиномиальное время» . Санкт-Петербургская математика. Дж . 15 : 813–835. дои : 10.1090/s1061-0022-04-00833-7 . МР 2044629 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

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