В теории графов рёберно-транзитивным ( англ. edge-transitive ) называется такой граф G , для двух любых рёбер которого e ₁ и e ₂ существует автоморфизм , отображающий e ₁ в e ₂ .

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

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

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

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

См. также

• (в геометрии)

Примечания

Литература

• Biggs N. Algebraic Graph Theory (англ.) . — 2nd ed. — Cambridge, 1993. — ISBN 0-521-45897-8 .
• Lauri J. , Scapellato R. Topics in Graph Automorphisms and Reconstruction (англ.) . — Cambridge University Press, 2003. — Vol. 54. — (London Mathematical Society. Student Texts). — ISBN 9780521529037 .

Ссылки

• Weisstein, Eric W. (англ.) на сайте Wolfram MathWorld .