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

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

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

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

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

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

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

См. также

Рёберная транзитивность^[англ.] (в геометрии)

Примечания

↑ ¹ ² ³ Biggs, 1993, с. 118.
↑ Lauri, 2003, с. 20-21.

Литература

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. Edge-transitive graph (англ.) на сайте Wolfram MathWorld.

[_21b5907c7edb5735-1] ¹ ² ³ Biggs, 1993, с. 118.

[_562ff0bb161dcceb-2] Lauri, 2003, с. 20-21.

[1]

[2]