В математической области теории графов , A пол-симметрический граф представляет собой неориентированный граф , который является край-транзитивен и регулярно , но не вершина-транзитивен . Другими словами, граф является полусимметричным, если каждая вершина имеет одинаковое количество инцидентных ребер и существует симметрия, соединяющая любое из ребер графа с любым другим его ребром, но существует пара вершин, такая что симметрия отображает первое во второе.
Свойства [ править ]
Полусимметричный граф должен быть двудольным , и его группа автоморфизмов должна действовать транзитивно на каждом из двух множеств вершин двудольного (на самом деле, регулярность не требуется для выполнения этого свойства). Например, на диаграмме графа Фолкмана, показанной здесь, зеленые вершины не могут быть отображены на красные никаким автоморфизмом, но каждые две вершины одного цвета симметричны друг другу.
История [ править ]
Полусимметричные графы впервые были изучены Э. Даубером, учеником Ф. Харари, в статье, которая больше не доступна, под названием «О линейно-симметричных, но не точечно-симметричных графах». Это заметил Джон Фолкман , чья статья, опубликованная в 1967 году, включает наименьший полусимметричный граф, ныне известный как граф Фолкмана , на 20 вершинах. [1] Термин «полусимметричный» впервые был использован Клином и др. в статье, опубликованной в 1978 г. [2]
Кубические графики [ править ]
Наименьший кубический полусимметричный граф (то есть такой, в котором каждая вершина инцидентна ровно трем ребрам) - это граф Грея с 54 вершинами. Впервые он был полусимметричным Боуэром (1968) . Драган Марушич и Александр Малнич доказали, что это наименьший кубический полусимметричный граф. [3]
Все кубические полусимметричные графы, содержащие до 768 вершин, известны. В соответствии с кондер , Malnič, Marusic и Potočnik, четыре маленьких возможные кубические пол-симметричные графами после Грея графа являются Iofinova-Иванов график , на 110 вершинах, в графе Любляны на 112 вершин, [4] графика на 120 вершин с обхватом 8 и 12-клетка Тутте . [5]
Ссылки [ править ]
- ^ Фолкман, J. (1967), "Обычные линейные симметричные графы", Журнал комбинаторной теории , 3 (3): 215-232, DOI : 10.1016 / S0021-9800 (67) 80069-3 CS1 maint: обескураженный параметр ( ссылка ).
- Перейти ↑ Klin, Lauri & Ziv-Av (2011). «Связи между двумя полусимметричными графами на 112 вершинах через призму ассоциативных схем» (PDF) . Проверено 17 августа 2015 года . Цитировать журнал требует
|journal=( помощь )CS1 maint: обескураженный параметр ( ссылка ) - ^ Bouwer, IZ (1968), "Ребро , но не вершина транзитивным кубический граф", Бюллетень канадского математического общества , 11 : 533-535, DOI : 10,4153 / CMB-1968-063-0.
- ^ Кондер, М .; Малнич, А .; Марушич, Д .; Писанский, Т .; Поточник, П. (2002), "Люблянский график" (PDF) , Препринты IMFM , Любляна: Институт математики, физики и механики, 40 (845) .
- ^ Кондер, Марстон ; Малнич, Александр; Марушич, Драган ; Potočnik, Primož (2006), "Перепись полусимметрических кубических графов на до 768 вершин", журнал алгебраической комбинаторики , 23 (3): 255-294, DOI : 10.1007 / s10801-006-7397-3 CS1 maint: обескураженный параметр ( ссылка ).
Внешние ссылки [ править ]
- Вайсштейн, Эрик В. «Полусимметричный граф» . MathWorld .
