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

Реберно-транзитивний граф — у теорії графів такий граф G, що для будь-яких двох ребер e₁ і e₂ графу G, існує автоморфізм графу G, який відображає e₁ в e₂[1].

Іншими словами, граф реберно-транзитивний, якщо його група автоморфізмів діє транзитивно на його ребрах.

Приклади та їх властивості

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

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

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

Див. також

Реберна транзитивність (в геометрії)

Примітки

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

Посилання

Weisstein, Eric W. Edge-transitive graph(англ.) на сайті Wolfram MathWorld.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[biggs-1] Norman Biggs. Algebraic Graph Theory. — Cambridge : 2nd ed, 1993. — ISBN 0-521-45897-8.

[ls03-2] Josef Lauri, Raffaele Scapellato. Topics in Graph Automorphisms and Reconstruction. — Cambridge University Press, 2003. — С. 20—21. — ISBN 9780521529037.