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

Семейства графов, определяемые их автоморфизмами
дистанционно-транзитивный	→	дистанционно-регулярный	←	строго регулярный
↓
симметричный (дуго-транзитивный)	←	t -транзитивный, $t \geq 2$		кососимметричный
↓
_{(если связаны)} вершинно- и реберно-транзитивные	→	реберно-транзитивные и регулярные	→	реберно-транзитивный
↓		↓		↓
вершинно-транзитивный	→	обычный	→	_{(если двудольный)} бирегулярный
↑
Граф Кэли	←	нулевой симметричный		асимметричный

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

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

Примеры и свойства [ править ]

Граф Грея является реберно-транзитивным и регулярным , но не вершинно-транзитивным .

К реберно-транзитивным графам относятся любой полный двудольный граф и любой симметричный граф , такой как вершины и ребра куба . ^[1] Симметричные графы также являются вершинно-транзитивными (если они связаны ), но в общем случае реберно-транзитивные графы не обязательно должны быть вершинно-транзитивными. Граф Грея является примером графа, который транзитивен по ребрам, но не транзитивен по вершинам. Все такие графы двудольные , ^[1] и , следовательно , могут быть окрашены только два цветом. ${\ displaystyle K_ {m, n}}$

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

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

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

См. Также [ править ]

Реберно-транзитивный (в геометрии)

Ссылки [ править ]

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

Внешние ссылки [ править ]

Вайсштейн, Эрик У. "Реберно-транзитивный граф" . MathWorld .

[biggs-1] Биггс, Норман (1993). Алгебраическая теория графов (2-е изд.). Кембридж: Издательство Кембриджского университета. п. 118. ISBN 0-521-45897-8.

[ls03-2] Лаури, Йозеф; Скапеллато, Раффаэле (2003), Темы автоморфизмов и реконструкции графов , Тексты студентов Лондонского математического общества, Cambridge University Press, стр. 20–21, ISBN 9780521529037.

[3] Уоткинс, Марк Э. (1970), «Связность транзитивных графов», Журнал комбинаторной теории , 8 : 23–29, DOI : 10.1016 / S0021-9800 (70) 80005-9 , MR 0266804

[1]