Обобщенный граф Петерсена

Семейство кубических графов, образованных из правильных и звездчатых многоугольников.

Граф Дюрера G (6, 2) .

В теории графов обобщенные графы Петерсена представляют собой семейство кубических графов , образованных соединением вершин правильного многоугольника с соответствующими вершинами звездчатого многоугольника . Они включают граф Петерсена и обобщают один из способов построения графа Петерсена. Семейство обобщенных графов Петерсена было введено в 1950 году Х.С.М. Коксетером ^[1] и получило свое название в 1969 году от Марка Уоткинса. ^[2]

Определение и обозначения

В обозначениях Уоткинса G ( n , k ) — граф с множеством вершин

${\displaystyle \{u_{0},u_{1},\ldots ,u_{n-1},v_{0},v_{1},\ldots ,v_{n-1}\}}$

и набор кромок

${\displaystyle \{u_{i}u_{i+1},u_{i}v_{i},v_{i}v_{i+k}\mid 0\leq i\leq n-1\}}$

где индексы следует читать по модулю n и k < n /2. Некоторые авторы используют обозначение GPG ( n , k ). Обозначение Коксетера для того же графа будет { n } + { n / k }, комбинация символов Шлефли для правильного n -угольника и звездчатого многоугольника , из которых формируется граф. Сам граф Петерсена равен G (5, 2) или {5} + {5/2}.

Любой обобщенный граф Петерсена также можно построить из графа напряжения с двумя вершинами, двумя петельками и еще одним ребром. ^[3]

Примеры

К числу обобщенных графов Петерсена относятся n -призма G ( n , 1), граф Дюрера G (6, 2), граф Мёбиуса-Кантора G (8, 3), додекаэдр G (10, 2), граф Дезарга граф G (10, 3) и граф Науру G (12, 5).

Четыре обобщенных графа Петерсена — 3-призма, 5-призма, граф Дюрера и G (7, 2) — входят в число семи графов, которые являются кубическими , 3-связными и хорошо покрытыми (это означает, что все графы являются кубическими, 3-связными и хорошо покрытыми ). их максимальные независимые множества имеют одинаковый размер). ^[4]

Характеристики

Один из трех гамильтоновых циклов в G (9, 2). Два других гамильтоновых цикла на том же графике симметричны при повороте рисунка на 40 °.

Это семейство графов обладает рядом интересных свойств. Например:

• G ( n , k ) вершинно-транзитивен (это означает, что он имеет симметрии, которые переводят любую вершину в любую другую вершину) тогда и только тогда, когда ( n , k ) = (10, 2) или k ²  ≡ ±1 (mod  n ) .
• G ( n , k ) транзитивен по ребрам (имеет симметрии, которые переводят любое ребро в любое другое ребро) только в следующих семи случаях: ( n , k ) = (4, 1), (5, 2), (8, 3), (10, 2), (10, 3), (12, 5), (24, 5). ^[5] Таким образом, эти семь графов являются единственными симметричными обобщенными графами Петерсена.
• G ( n , k ) двудольный тогда и только тогда, когда n четно, а k нечетно.
• G ( n , k ) является графом Кэли тогда и только тогда, когда k ²  ≡ 1 (mod  n ).
• G ( n , k ) является гипогамильтоновым , когда n конгруэнтно 5 по модулю 6 и k = 2, n - 2 или ( n ± 1)/2 (эти четыре выбора k приводят к изоморфным графам). Оно также не является гамильтоновым , когда n делится на 4, по крайней мере, равно 8, и k = n /2. Во всех остальных случаях он имеет гамильтонов цикл . ^[6] Когда n конгруэнтно 3 по модулю 6, G ( n , 2) имеет ровно три гамильтоновых цикла. ^[7] Для G ( n , 2) количество гамильтоновых циклов можно вычислить по формуле, которая зависит от класса конгруэнтности n по модулю 6 и включает числа Фибоначчи . ^[8]
• Каждый обобщенный граф Петерсена является графом единичных расстояний . ^[9]

Изоморфизмы

G ( n , k ) изоморфен G ( n , l ) тогда и только тогда, когда k=l или kl  ≡ ±1 (mod  n ). ^[10]

Обхват

Обхват G ( n , k ) не менее 3 и не более 8, в частности: ^[11]

${\displaystyle g(G(n,k))\leq \min \left\{8,k+3,{\frac {n}{\gcd(n,k)}}\right\}.}$

Таблица с точными значениями обхватов:

Хроматическое число и хроматический индекс

Будучи регулярными , по теореме Брукса их хроматическое число не может быть больше их степени . Обобщенные графы Петерсена кубические, поэтому их хроматическое число может быть как 2, так и 3. Точнее:

${\displaystyle \chi (G(n,k))={\begin{cases}2&2\mid n\land 2\nmid k\\3&2\nmid n\lor 2\mid k\\\end{cases}}}$

Где обозначает логическое И , а логическое ИЛИ . Например, хроматическое число равно 3. ${\displaystyle \land }$ ${\displaystyle \lor }$ ${\displaystyle G(5,2)}$

• 
  3-раскраска графа Петерсена или ${\displaystyle G(5,2)}$
• 
  2-раскраска графа Дезарга или ${\displaystyle G(10,3)}$
• 
  3-раскраска графа Дюрера или ${\displaystyle G(6,2)}$

Граф Петерсена , будучи снарком , имеет хроматический индекс 4. Все остальные обобщенные графы Петерсена имеют хроматический индекс 3. ^[12]

Обобщенный граф Петерсена G (9, 2) — один из немногих известных графов, имеющий только одну 3-реберную раскраску . ^[13]

• 
  4-реберная раскраска графа Петерсена или ${\displaystyle G(5,2)}$
• 
  Трехреберная раскраска графа Дюрера или ${\displaystyle G(6,2)}$
• 
  Трехгранная раскраска додекаэдра или ${\displaystyle G(10,2)}$
• 
  Трехреберная раскраска графа Дезарга или ${\displaystyle G(10,3)}$
• 
  Трехреберная раскраска графа Науру или ${\displaystyle G(12,5)}$

Граф Петерсена сам по себе является единственным обобщенным графом Петерсена, который не раскрашивается в 3 ребра . ^[14]

Идеальные раскраски

Перенумерованы все допустимые матрицы всех совершенных 2-раскрасок графов G ( n , 2 ) и G ( n , 3 ). ^[15]

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

1. Коксетер, HSM (1950), «Самодвойственные конфигурации и регулярные графы», Бюллетень Американского математического общества , 56 (5): 413–455, doi : 10.1090/S0002-9904-1950-09407-5.
2. Уоткинс, Марк Э. (1969), «Теорема о раскрасках Тейта с применением к обобщенным графам Петерсена», Журнал комбинаторной теории , 6 (2): 152–164, doi : 10.1016/S0021-9800(69) 80116-Х.
3. Гросс, Джонатан Л.; Такер, Томас В. (1987), Топологическая теория графов , Нью-Йорк: Wiley. Пример 2.1.2, стр.58.
4. Кэмпбелл, SR; Эллингем, Миннесота ; Ройл, Гордон Ф. (1993), «Характеристика хорошо покрытых кубических графов», Журнал комбинаторной математики и комбинаторных вычислений , 13 : 193–212, MR  1220613.
5. Фрухт, Р .; Грейвер, Дж. Э.; Уоткинс, М.Э. (1971), «Группы обобщенных графов Петерсена», Труды Кембриджского философского общества , 70 (2): 211–218, doi : 10.1017/S0305004100049811.
6. Alspach, BR (1983), "Классификация гамильтоновых обобщенных графов Петерсена", Журнал комбинаторной теории , серия B, 34 (3): 293–312, doi : 10.1016/0095-8956(83)90042-4 , MR  0714452.
7. Томасон, Эндрю (1982), «Кубические графы с тремя гамильтоновыми циклами не всегда однозначно раскрашиваются по краям», Journal of Graph Theory , 6 (2): 219–221, doi : 10.1002/jgt.3190060218.
8. Швенк, Аллен Дж. (1989), «Перечисление гамильтоновых циклов в некоторых обобщенных графах Петерсена», Журнал комбинаторной теории , серия B, 47 (1): 53–59, doi : 10.1016/0095-8956(89)90064 -6 , МР  1007713.
9. Житник, Арьяна; Хорват, Борис; Писански, Томаж (2010), Все обобщенные графы Петерсена представляют собой графы единичных расстояний (PDF) , препринты IMFM, том. 1109.
10. Стеймле, Алиса; Стейтон, Уильям (2009), «Классы изоморфизма обобщенных графов Петерсена», Discrete Mathematics , 309 (1): 231–237, doi : 10.1016/j.disc.2007.12.074
11. Ферреро, Даниэла; Хануш, Сара (2014), «Связность компонентов обобщенных графов Петерсена» (PDF) , International Journal of Computer Mathematics , 91 (9): 1940–1963, doi : 10.1080/00207160.2013.878023, ISSN  0020-7160, заархивировано из оригинал (PDF) от 20 октября 2018 г. , получено 20 октября 2018 г.
12. Кастанья, Фрэнк; Принс, Герт Калеб Эрнст (1972), «Каждый обобщенный граф Петерсена имеет раскраску Тейта», Pacific Journal of Mathematics , 40 (1): 53–58, doi : 10.2140/pjm.1972.40.53 , ISSN  0030-8730, MR  0304223, Збл  0236.05106
13. Боллобас, Бела (2004), Экстремальная теория графов , Дувр, стр. 233. Перепечатка издания Academic Press 1978 года.
14. Кастанья, Фрэнк; Принс, Герт (1972), «Каждый обобщенный граф Петерсена имеет раскраску Тейта», Pacific Journal of Mathematics , 40 : 53–58, doi : 10.2140/pjm.1972.40.53.
15. Карами, Хамед (2022), «Совершенные 2-раскраски обобщенного графа Петерсена GP(n,3)», Электронный журнал теории графов и приложений , 10 : 239–245, arXiv : 2009.07120 , doi : 10.5614/ejgta. 2022.10.1.16.