Нуль-симметричный граф
В математической области теории графов — нуль-симметричный граф это связный граф , в котором каждая вершина имеет ровно три инцидентных ребра и для каждых двух вершин существует уникальная симметрия, переводящая одну вершину в другую. Такой граф является вершинно-транзитивным графом, но не может быть реберно-транзитивным графом : количество симметрий равно количеству вершин, слишком мало, чтобы каждое ребро можно было перевести в любое другое ребро. [1]
Название для этого класса графов было придумано Р. М. Фостером в письме 1966 года HSM Coxeter . [2] В контексте теории групп нуль-симметричные графы также называются графическими регулярными представлениями своих групп симметрии. [3]
Примеры [ править ]
Наименьший нуль-симметричный граф — это непланарный граф с 18 вершинами. [4] Его обозначение LCF : [5,−5] 9 .
Среди плоских графов усеченные кубооктаэдрические и усеченные икосододекаэдрические графы также являются нуль-симметричными. [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 , МР 0658666
- ^ Коксетер, Фрухт и Пауэрс (1981) , стр. ix.
- ^ Лаури, Йозеф; Скапеллато, Раффаэле (2003), Темы автоморфизмов и реконструкции графов , Тексты для студентов Лондонского математического общества, Cambridge University Press, стр. 66, ISBN 9780521529037 .
- ^ Коксетер, Фрухт и Пауэрс (1981) , рисунок 1.1, с. 5.
- ^ Coxeter, Frucht & Powers (1981) , стр. 75 и 80.
- ^ Коксетер, Фрухт и Пауэрс (1981) , стр. 55.
- ^ Кондер, Марстон, Делавэр ; Писански, Томаж ; Житник, Арьяна (2017), «Вершинно-транзитивные графы и их типы дуг», Ars Mathematica Contemporanea , 12 (2): 383–413, arXiv : 1505.02029 , doi : 10.26493/1855-3974.1146.f96 , MR 3646702
- ^ Поточник, Примож; Спига, Пабло; Веррет, Габриэль (2013), «Кубические вершинно-транзитивные графы с числом вершин до 1280», Journal of Символические вычисления , 50 : 465–477, arXiv : 1201.5317 , doi : 10.1016/j.jsc.2012.09.002 , MR 2996891 .
- ^ Коксетер, Фрухт и Пауэрс (1981) , стр. 10.