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

В теории графов циркулянтным графом называется неориентированный граф, имеющий циклическую группу симметрий, которая включает симметрию, переводящую любую вершину в любую другую вершину.

Граф Пэли 13-го порядка как пример циркулянтного графа.
Корона с шестью, восемью и десятью вершинами.

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

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

  • Автоморфизм группы графа содержит циклическую подгруппу, которая действует транзитивно на вершинах графа.
  • Граф имеет матрицу смежности, являющуюся циркулянтом.
  • вершин графа можно пронумеровать числами от 0 до n 1 таким образом, что если две вершины с номерами и смежны, то любые две вершины с номерами и (z x + y) mod n тоже смежны.
  • Граф можно нарисовать (с возможными пересечениями рёбер) так, что его вершины лежат в углах правильного многоугольника и любой поворот многоугольника в себя является симметрией рисунка (получаем тот же рисунок).

Примеры

Любой цикл является циркулянтным графом, как и любая корона.

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

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

Если два числа и взаимно просты, то m × n ладейный граф (граф, имеющий вершину в каждой клетке шахматной доски m × n и рёбра между любыми двумя клетками, если ладья может перейти с одной клетки на другую за один ход) является циркулянтным графом. Это является следствием того, что его симметрии содержат в качестве подгруппы циклическую группу {{{1}}}. Как обобщение этого случая, прямое произведение графов между любыми циркулянтными графами с и вершинами даёт в результате циркулянтный граф[1].

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

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

Циркулянтный граф (или , или ) с прыжками определяется как граф с узлами, пронумерованными числами и каждый узел смежен с 2k узлами по модулю .

  • Граф связан тогда и только тогда, когда НОД.
  • Если фиксировнные целые, то число остовных деревьев , где удовлетворяет рекуррентному соотношению порядка .
    • В частности, , где  — n-ое число Фибоначчи.

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

Самодополнительный граф — это граф, в котором удаление существующих рёбер и добавление отсутствующих даёт граф, изоморфный исходному.

Например, циклический граф с пятью вершинами самодополнителен и является также циркулянтным. В более общем виде, любой граф Пэли является самодополнительным циркулянтным графом[3]. Хорст Сакс показал, что если число обладает свойством, что любой простой делитель сравним с 1 по модулю 4, то существует самодополнительный циркулянтный граф с вершинами. Он высказал гипотезу, что это условие необходимо, то есть при других значениях самодополнительные циркулянтные графы не существуют[1][3]. Гипотеза доказана 40 лет позже Вилфредом (Vilfred)[1].

Гипотеза Адамса

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

Пусть  — целое, взаимно простое c , и пусть  — любое целое. Тогда линейная функция ax + b преобразует циркулянтную нумерацию в другую циркулянтную нумерацию. Андраш Адам (András Ádám) высказал гипотезу, что линейное отображение — единственный способ перенумерации вершин графа, сохраняющее свойство циркулянтности. То есть, если и  — два изоморфных циркулянтных графа с различными нумерациями, то существует линейное преобразование, переводящее нумерацию для в нумерацию для . Однако, как выяснилось, гипотеза Адама не верна. Контрпримером служат графы и с 16-ю вершинами в каждом; вершина в соединена с шестью соседями x ± 1, x ± 2, и x ± 7 (по модулю 16), в то время как в шесть соседей — это x ± 2, x ± 3, и x ± 5 (по модулю 16). Эти два графа изоморфны, но их изоморфизм нельзя получить посредством линейного преобразования.[1]

Примечания

  1. V. Vilfred. Graph Theory and its Applications (Anna University, Chennai, March 14–16, 2001) / editors: R. Balakrishnan, G. Sethuraman, Robin J. Wilson. — Alpha Science, 2004. С. 34—36.
  2. Small Ramsey Numbers Архивная копия от 18 января 2012 на Wayback Machine, Stanisław P. Radziszowski, Electronic J. Combinatorics, dynamic survey updated 2009.
  3. Horst Sachs. Über selbstkomplementäre Graphen // Publicationes Mathematicae Debrecen. — 1962. Т. 9. С. 270—288.

Ссылки

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.