Полусимметричный граф - Semi-symmetric graph

В Граф Фолькмана, наименьший полусимметричный граф.
Семейства графов, определяемые их автоморфизмами
дистанционно-переходный→дистанционно-регулярный←строго регулярный
↓
симметричный (дуго-транзитивный)←т-переходный, т ≥ 2кососимметричный
↓
(если подключен)
вершинно- и реберно-транзитивные		→реберно-транзитивные и регулярные→реберно-транзитивный
↓↓↓
вершинно-транзитивный→обычный→(если двудольный)
двурегулярный
↑
Граф Кэли←нулевой симметричныйасимметричный

в математический поле теория графов, а полусимметричный граф является неориентированный граф то есть реберно-транзитивный и обычный, но нет вершинно-транзитивный. Другими словами, граф является полусимметричным, если каждая вершина имеет одинаковое количество инцидентных ребер, и существует симметрия, соединяющая любое из ребер графа с любым другим его ребром, но существует пара вершин, такая что симметрия отсутствует. отображает первое во второе.

Характеристики

Полусимметричный граф должен быть двудольный, и это группа автоморфизмов должен действовать переходно на каждом из двух множеств вершин двудольного (на самом деле, для выполнения этого свойства регулярность не требуется). Например, на диаграмме Граф Фолькмана Как показано здесь, зеленые вершины не могут быть преобразованы в красные никаким автоморфизмом, но каждые две вершины одного цвета симметричны друг другу.

История

Полусимметричные графы впервые были изучены Э. Даубером, учеником Ф. Харари, в статье, которая больше не доступна, под названием «О линейно-симметричных, но не точечно-симметричных графах». Это видели Джон Фолкман, чья статья, опубликованная в 1967 году, включает наименьший полусимметричный граф, ныне известный как Граф Фолькмана, на 20 вершинах.[1]Термин «полусимметричный» впервые употребил Клин. и другие. в статье, опубликованной в 1978 г.[2]

Кубические графы

Наименьший кубический полусимметричный граф (то есть такой, в котором каждая вершина инцидентна ровно трем ребрам) - это Серый график на 54 вершинах. Впервые было обнаружено, что полусимметричный Бауэр (1968). Было доказано, что это самый маленький кубический полусимметричный граф. Драган Марушич и Александр Малнич.[3]

Все кубические полусимметричные графы, содержащие до 768 вершин, известны. В соответствии с Кондер, Малнич, Марушич и Поточник, четыре наименьших возможных кубических полусимметрических графа после графа Грея - это граф Иофиновой – Иванова на 110 вершинах, Любляна график на 112 вершинах,[4] граф на 120 вершинах с обхватом 8 и Тутте 12 клеток.[5]

Рекомендации

  1. ^ Фолькман, Дж. (1967), "Правильные линейно-симметричные графы", Журнал комбинаторной теории, 3 (3): 215–232, Дои:10.1016 / S0021-9800 (67) 80069-3.
  2. ^ Клин, Лаури и Зив-Ав (2011). «Связи между двумя полусимметричными графами на 112 вершинах через призму ассоциативных схем» (PDF). Получено 17 августа 2015. Цитировать журнал требует | журнал = (помощь)
  3. ^ Бауэр, И. З. (1968), "Реберный, но не вершинный транзитивный кубический граф", Бюллетень Канадского математического общества, 11: 533–535, Дои:10.4153 / CMB-1968-063-0.
  4. ^ Кондер, М.; Малнич, А .; Марушич, Д.; Писанский, Т.; Поточник, П. (2002), "Люблянский график" (PDF), Препринты IMFM, Любляна: Институт математики, физики и механики, 40 (845).
  5. ^ Кондер, Марстон; Малнич, Александр; Марушич, Драган; Поточник, Примож (2006), "Перепись полусимметричных кубических графов с числом вершин до 768", Журнал алгебраической комбинаторики, 23 (3): 255–294, Дои:10.1007 / s10801-006-7397-3.

внешняя ссылка