stringtranslate.com

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

В математической области теории графов реберно -транзитивный граф — это граф G, такой что для любых двух ребер e 1 и e 2 графа G существует автоморфизм графа G , который отображает e 1 в e 2 . [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 Biggs, Norman (1993). Алгебраическая теория графов (2-е изд.). Кембридж: Cambridge University Press. стр. 118. ISBN 0-521-45897-8.
  2. ^ Лаури, Йозеф; Скапеллато, Раффаэле (2003), Темы по автоморфизмам и реконструкции графов, Студенческие тексты Лондонского математического общества, Издательство Кембриджского университета, стр. 20–21, ISBN 9780521529037.
  3. ^ Ньюман, Хизер А.; Миранда, Гектор; Нараян, Даррен А. (2019). «Реберно-транзитивные графы и комбинаторные конструкции». Involve: A Journal of Mathematics . 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

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