Полутранзитивный граф - Half-transitive graph

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

в математический поле теория графов, а полупереходный граф это график это оба вершинно-транзитивный и реберно-транзитивный, но нет симметричный.[1] Другими словами, граф является полупереходным, если его группа автоморфизмов действует переходно как на его вершинах, так и на его ребрах, но не на упорядоченных парах связанных вершин.

В Граф Холта - наименьший полупереходный граф. Отсутствие отражательной симметрии на этом чертеже подчеркивает тот факт, что края не эквивалентны их инверсии.

Каждый подключен симметричный граф должно быть вершинно-транзитивный и реберно-транзитивный, и обратное верно для графов нечетной степени,[2] так что полупереходных графов нечетной степени не существует. Однако существуют полупереходные графы четной степени.[3] Наименьший полупереходный граф - это Граф Холта, со степенью 4 и 27 вершинами.[4][5]

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

  1. ^ Gross, J.L .; Йеллен, Дж. (2004). Справочник по теории графов. CRC Press. п. 491. ISBN  1-58488-090-2.
  2. ^ Бабай, Л. (1996). «Группы автоморфизмов, изоморфизм, реконструкция». В Graham, R; Грётшель, М; Ловас, Л. (ред.). Справочник по комбинаторике. Эльзевир.
  3. ^ Бауэр, З. "Вершинные и реберные транзитивные, но не 1-транзитивные графы". Канад. Математика. Бык. 13, 231–237, 1970.
  4. ^ Биггс, Норман (1993). Алгебраическая теория графов (2-е изд.). Кембридж: Издательство Кембриджского университета. ISBN  0-521-45897-8.
  5. ^ Холт, Дерек Ф. (1981). «Граф, который транзитивен по ребрам, но не транзитивен по дуге». Журнал теории графов. 5 (2): 201–204. Дои:10.1002 / jgt.3190050210..