Реберно-транзитивний граф — у теорії графів такий граф G, що для будь-яких двох ребер e1 і e2 графа G, існує автоморфізм графа G, який відображає e1 в e2.
Іншими словами, граф реберно-транзитивний, якщо його група автоморфізмів діє транзитивно на його ребрах.
Приклади та їх властивості
Реберно-транзитивні графи включають в себе усі повні двочасткові графи , та всі симетричні графи, такі як вершини й ребра куба. Симетричні графи вважаються вершинно-транзитивними (якщо вони зв'язні), але в загальному випадку реберно-транзитивні графи не обов'язково вершинно-транзитивні. Граф Грея є прикладом графа, який є реберно-транзитивним, але не вершинно-транзитивним. Всі такі графи є двочастковими і тому вони можуть бути розфарбовані всього в два кольори.
Реберно-транзитивний граф, який є також регулярним, але не вершинно-транзитивним, називається напівсиметричним. Граф Грея знову служить прикладом. Реберно-транзитивний граф повинен бути двочастковим та або напівсиметричним, або бірегулярним.
Див. також Реберна транзитивність (в геометрії)
Примітки
Посилання