Реберно-транзитивный граф
В математической области теории графов реберно транзитивный граф — это граф 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]
См. также [ править ]
- Крайно-транзитивный (в геометрии)
Ссылки [ править ]
- ^ Перейти обратно: а б с Биггс, Норман (1993). Алгебраическая теория графов (2-е изд.). Кембридж: Издательство Кембриджского университета. п. 118. ИСБН 0-521-45897-8 .
- ^ Лаури, Йозеф; Скапеллато, Раффаэле (2003), Темы автоморфизмов и реконструкции графов , Тексты для студентов Лондонского математического общества, Cambridge University Press, стр. 20–21, ISBN 9780521529037 .
- ^ Ньюман, Хизер А.; Миранда, Гектор; Нараян, Даррен А. (2019). «Реберно-транзитивные графы и комбинаторные схемы». Включите: Математический журнал . 12 (8): 1329–1341. arXiv : 1709.04750 . дои : 10.2140/involve.2019.12.1329 . S2CID 119686233 .
- ^ Уоткинс, Марк Э. (1970), «Связность транзитивных графов», Журнал комбинаторной теории , 8 : 23–29, doi : 10.1016/S0021-9800(70)80005-9 , MR 0266804