Циркулянтный график
- Циркулирующий граф — неориентированный граф, на который воздействует циклическая группа симметрий.
- Циркулянтные графы могут быть описаны несколькими эквивалентными способами.
- Группа автоморфизмов графа включает в себя циклическую подгруппу, которая транзитивно воздействует на вершины графа.
- Графы Пейли порядка n являются циркулянтными, если их вершины пронумерованы от 0 до n — 1 и две вершины смежны, если их разность равна квадратичному вычету по модулю n.
- Многие известные нижние оценки чисел Рамсея взяты из примеров циркулянтных графов с небольшими максимальными кликами и независимыми множествами.
- Самодополняющие циркулянты — это графы, в которых замена каждого ребра на не-ребро и наоборот приводит к получению изоморфного графа.
- Гипотеза Адама утверждает, что линейные отображения являются единственными способами перенумерации циркулянтного графа с сохранением свойства циркулянта.
- Гипотеза Тойды уточняет гипотезу Адама, рассматривая только особый класс циркулянтных графов, в которых все различия между соседними вершинами графа относительно просты по отношению к числу вершин.
Полный текст статьи: