В математической области теории графов реберно - транзитивный граф — это граф G такой , что для любых двух ребер e1 и e2 графа G существует автоморфизм G , который отображает e1 в e2 . [1]
Другими словами, граф транзитивен по ребрам, если его группа автоморфизмов действует транзитивно на его ребрах.
Число связных простых реберно-транзитивных графов на n вершинах равно 1, 1, 2, 3, 4, 6, 5, 8, 9, 13, 7, 19, 10, 16, 25, 26, 12, 28.. .(последовательность A095424 в OEIS )
Реберно-транзитивные графы включают в себя все симметричные графы , такие как вершины и ребра куба . [1] Симметричные графы также являются вершинно-транзитивными (если они связны ), но в общем случае реберно-транзитивные графы не обязательно должны быть вершинно-транзитивными. Каждый связный реберно-транзитивный граф, который не является вершинно-транзитивным, должен быть двудольным [ 1] (и, следовательно, может быть раскрашен только в два цвета) и либо полусимметричным, либо бирегулярным . [2]
Примеры реберных, но не вершинных транзитивных графов включают полные двудольные графы , где m ≠ n, включая звездчатые графы . Для графов с n вершинами существует (n-1)/2 таких графов для нечетного n и (n-2) для четного n. Дополнительные реберные транзитивные графы, которые не являются симметричными, в некоторых случаях могут быть сформированы как подграфы этих полных двудольных графов. Подграфы полных двудольных графов K m,n существуют, когда m и n имеют общий коэффициент больше 2. Когда наибольший общий делитель равен 2, подграфы существуют, когда 2n/m четно или если m = 4 и n нечетно кратно 6. [3] Таким образом , реберные транзитивные подграфы существуют для K 3,6 , K 4,6 и K 5,10 , но не K 4,10 . Альтернативная конструкция для некоторых реберно-транзитивных графов состоит в добавлении вершин в середины ребер симметричного графа с v вершинами и e ребрами, создавая двудольный граф с e вершинами порядка 2 и v порядка 2e/v.
Реберно-транзитивный граф, который также является регулярным , но все же не вершинно-транзитивным, называется полусимметричным . Граф Грея , кубический граф с 54 вершинами, является примером регулярного графа, который является транзитивным по ребрам, но не транзитивным по вершинам. Граф Фолкмана , граф квартики на 20 вершинах, является наименьшим таким графом.
Связность вершин реберно-транзитивного графа всегда равна его минимальной степени . [4]