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

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

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

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

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

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

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

См. также

• Шаблон:Не переведено 5 (в геометрии)

Литература

• Шаблон:Книга
• Шаблон:Книга

Ссылки

• Шаблон:MathWorld