stringtranslate.com

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

В математической области теории графов реберно -транзитивный граф — это граф 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]

Смотрите также

Рекомендации

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

Внешние ссылки