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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

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

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

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

Смотрите также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. 1 2 3 Norman Biggs. Algebraic Graph Theory. — 2nd ed.. — Cambridge, 1993. — ISBN 0-521-45897-8.
  2. Josef Lauri , Raffaele Scapellato Topics in Graph Automorphisms and Reconstruction. — Cambridge University Press, 2003.. — С. 20—21. — ISBN 9780521529037.

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