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

---

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

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

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

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

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

---