Реберно-транзитивный граф - Edge-transitive graph

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

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

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

Примеры и свойства

В Серый график реберно-транзитивно и обычный, но нет вершинно-транзитивный.

Краевые транзитивные графы включают любые полный двудольный граф , и любые симметричный граф, например, вершины и ребра куб.[1] Симметричные графы также вершинно-транзитивный (если они связаны ), но в общем случае графы с транзитивными ребрами не обязательно должны быть транзитивными по вершинам. В Серый график это пример графа, который транзитивен по ребрам, но не по вершинам. Все такие графики двудольный,[1] и, следовательно, может быть цветной всего с двумя цветами.

Реберно-транзитивный граф, который также обычный, но не вершинно-транзитивным, называется полусимметричный. В Серый график снова дает пример. Каждый реберно-транзитивный граф, который не является вершинно-транзитивным, должен быть двудольный и либо полусимметричный, либо двурегулярный.[2]

В связность вершин реберно-транзитивного графа всегда равно его минимальная степень.[3]

Марстон Кондер составил Полный список всех связных реберно-транзитивных графов с числом вершин до 47 и Полный список всех связных реберно-транзитивных двудольных графов с числом вершин до 63.

Смотрите также

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

  1. ^ а б c Биггс, Норман (1993). Алгебраическая теория графов (2-е изд.). Кембридж: Издательство Кембриджского университета. п. 118. ISBN  0-521-45897-8.
  2. ^ Лаури, Йозеф; Скапеллато, Рафаэле (2003), Темы автоморфизмов и реконструкции графов, Тексты студентов Лондонского математического общества, Cambridge University Press, стр. 20–21, ISBN  9780521529037.
  3. ^ Уоткинс, Марк Э. (1970), "Связность транзитивных графов", Журнал комбинаторной теории, 8: 23–29, Дои:10.1016 / S0021-9800 (70) 80005-9, МИСТЕР  0266804

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