Полусимметричный граф
В математической области теории графов полусимметричный граф — это неориентированный граф , транзитивный по ребрам и регулярный , но не транзитивный по вершинам . Другими словами, граф является полусимметричным, если каждая вершина имеет одинаковое количество инцидентных ребер и существует симметрия, переводящая любое ребро графа в любое другое его ребро, но существует некоторая пара вершин, такая что симметрия отсутствует. отображает первое во второе.
Свойства [ править ]
Полусимметричный граф должен быть двудольным , а его группа автоморфизмов должна действовать транзитивно на каждом из двух множеств вершин двудольного деления (фактически, для выполнения этого свойства регулярность не требуется). Например, на диаграмме графа Фолкмана, показанной здесь, зеленые вершины не могут быть отображены в красные ни одним автоморфизмом, но каждые две вершины одного цвета симметричны друг другу.
История [ править ]
Полусимметричные графы впервые были изучены Э. Даубером, учеником Ф. Харари, в уже не изданной статье под названием «Олинейно-, но не точечно-симметричные графы». Это увидел Джон Фолкман , чья статья, опубликованная в 1967 году, включает наименьший полусимметричный граф, ныне известный как граф Фолкмана , на 20 вершинах. [1] Термин «полусимметричный» впервые был использован Клином и соавт. в статье, опубликованной в 1978 году. [2]
Кубические графы [ править ]
Наименьшим кубическим полусимметричным графом (то есть таким, в котором каждая вершина инцидентна ровно трем ребрам) является граф Грея на 54 вершинах. Впервые его полусимметричность была обнаружена Бауэром (1968) . и Александр Мальнич доказали, что это самый маленький кубический полусимметричный граф Драган Марушич . [3]
Известны все кубические полусимметричные графы с числом вершин до 10 000. Согласно Кондеру , Мальничу, Марушичу и Поточнику, четырьмя наименьшими возможными кубическими полусимметричными графами после графа Грея являются граф Иофинова-Иванова на 110 вершинах, Люблянский граф на 112 вершинах, [4] граф на 120 вершинах с обхватом 8 и клеткой Тутте 12 . [5]
Ссылки [ править ]
- ^ Фолкман Дж. (1967), «Регулярные линейно-симметричные графы», Журнал комбинаторной теории , 3 (3): 215–232, doi : 10.1016/S0021-9800(67)80069-3 .
- ^ Клин, Михаил; Лаури, Йозеф; Зив-Ав, Матан (2012), «Связи между двумя полусимметричными графами на 112 вершинах посредством ассоциативных схем» (PDF) , Journal of Символические вычисления , 47 (10): 1175–1191, doi : 10.1016/j.jsc.2011.12. 040 , МР 2926121
- ^ Бауэр, И.З. (1968), «Реберный, но не вершинный транзитивный кубический граф», Canadian Mathematical Bulletin , 11 (4): 533–535, doi : 10.4153/CMB-1968-063-0 .
- ^ Кондер, М .; Мальнич, А.; Марушич, Д. ; Писански, Т. ; Поточник, П. (2002), «График Любляны» (PDF) , Препринты МВФМ , том. 40, ну. 845, Любляна: Институт математики, физики и механики .
- ^ Кондер, Марстон ; Мальнич, Александр; Марушич, Драган ; Поточник, Примож (2006), «Перепись полусимметричных кубических графов с числом вершин до 768», Журнал алгебраической комбинаторики , 23 (3): 255–294, doi : 10.1007/s10801-006-7397-3 .