В математической области теории графов , A нулевой симметрический граф является связным графом , в котором каждая вершина имеет ровно три падающие края , и для каждых двух вершин, существует единственная симметрия с одной вершины к другой. Такой граф является вершинно-транзитивным графом, но не может быть реберно-транзитивным графом : количество симметрий равно количеству вершин, слишком мало, чтобы соединить каждое ребро с каждым другим ребром. [1]
Название этого класса графов было придумано Р. М. Фостером в 1966 году в письме HSM Кокстеру . [2] Эти графы в настоящее время называются кубическими GRR (графические регулярные представления). [3]
Примеры [ править ]
Наименьший нулевой симметричный граф - это неплоский граф с 18 вершинами. [4] Его обозначение LCF - [5, −5] 9 .
Среди плоских графов , на усеченной кубооктаэдрический и усеченную icosidodecahedral графика также нулевой симметричная. [5]
Все эти примеры являются двудольными графами . Однако существуют более крупные примеры недвудольных графов с нулевой симметрией. [6]
В этих примерах также есть три разных класса симметрии (орбиты) ребер. Однако существуют нуль-симметричные графы только с двумя орбитами ребер. Наименьший такой граф имеет 20 вершин с обозначением LCF [6,6, -6, -6] 5 . [7]
Свойства [ править ]
Каждый конечный нуль-симметричный граф - это граф Кэли , свойство, которое не всегда выполняется для кубических вершинно-транзитивных графов в более общем смысле и помогает в решении комбинаторных задач перечисления, касающихся нуль-симметричных графов. Имеется 97687 нуль-симметричных графов с числом вершин до 1280. Эти графы составляют 89% кубических графов Кэли и 88% всех связных вершинно-транзитивных кубических графов с одинаковым количеством вершин. [8]
 | Нерешенная задача по математике : Каждый ли конечный нуль-симметричный граф содержит гамильтонов цикл ? (больше нерешенных задач по математике) |
Все известные конечные связные нуль-симметричные графы содержат гамильтонов цикл , но неизвестно, обязательно ли каждый конечный связный нуль-симметричный граф гамильтоновым. [9] Это частный случай гипотезы Ловаса о том, что (за пятью известными исключениями, ни одно из которых не является нуль-симметричным) каждый конечный связный вершинно-транзитивный граф и каждый конечный граф Кэли является гамильтоновым.
См. Также [ править ]
- Полусимметричный граф , графы, которые имеют симметрии между каждыми двумя ребрами, но не между каждыми двумя вершинами (изменение ролей ребер и вершин в определении нулевых симметричных графов)
Ссылки [ править ]
- ^ Коксетер, Гарольд Скотт Макдональд ; Фрухт, Роберто ; Пауэрс, Дэвид Л. (1981), Нуль-симметричные графы , Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], Нью-Йорк-Лондон, ISBN 0-12-194580-4, MR 0658666
- ↑ Coxeter, Frucht & Powers (1981) , стр. ix.
- ^ Лаури, Йозеф; Скапеллато, Раффаэле (2003), Темы автоморфизмов и реконструкции графов , Студенческие тексты Лондонского математического общества, Cambridge University Press, стр. 20–21, ISBN 9780521529037.
- ^ Coxeter, Frucht & Powers (1981) , рисунок 1.1, стр. 5.
- ↑ Coxeter, Frucht & Powers (1981) , стр. 75 и 80.
- ↑ Coxeter, Frucht & Powers (1981) , стр. 55.
- ^ Кондер, Марстон DE ; Писанский, Томаж ; Žitnik, Arjana (2017), "Vertex-переходные графы и их угловых типов", Арс Mathematica Contemporanea , 12 (2): 383-413, Arxiv : +1505,02029 , DOI : 10,26493 / 1855-3974.1146.f96 , МР 3646702
- ^ Potočnik, Primož; Спига, Пабло; Verret, Габриэль (2013), "Cubic вершинных-транзитивные графы на до 1280 вершин", журнал символьных вычислений , 50 : 465-477, Arxiv : 1201,5317 , DOI : 10.1016 / j.jsc.2012.09.002 , MR 2996891 .
- ↑ Coxeter, Frucht & Powers (1981) , стр. 10.
