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

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

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

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

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

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

\{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 ( n , k ) вершинно-транзитивен (это означает, что он имеет симметрии, которые переводят любую вершину в любую другую вершину) тогда и только тогда, когда ( n , k ) = (10, 2) или k ² ≡ ±1 (против 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 (против 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]

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

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

Состояние	Обхват
$n=3k$	3
$n=4k$	4
$k=1$	4
$n=5k$	5
$n=5k/2$
$k=2$
$n=6k$	6
$k=3$
$n=2k+2$
$n=7k$	7
$n=7k/2$
$n=7k/3$
$k=4$
$n=2k+3$
$n=3k\pm 2$
в противном случае	8

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

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

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

Где $\land$ обозначает логическое И , а $\lor$ логическое ИЛИ . Здесь, $\mid$ обозначает делимость, а $\nmid$ означает его отрицание. Например, хроматическое число $G(5,2)$ это 3.

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

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

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

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

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

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

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

Допустимые матрицы
	Г(п, 2)	Г(п, 3)
${\begin{bmatrix}2&1\\1&2\end{bmatrix}}$	Все графики	Все графики
${\begin{bmatrix}2&1\\2&1\end{bmatrix}}$	Просто G ( 3м , 2 )	Нет графиков
${\begin{bmatrix}1&2\\2&1\end{bmatrix}}$	Нет графиков	Просто G ( 2м , 3 )
${\begin{bmatrix}0&3\\1&2\end{bmatrix}}$	Нет графиков	Просто G ( 4м , 3 )
${\begin{bmatrix}0&3\\2&1\end{bmatrix}}$	Просто G ( 5м , 2 )	Просто G ( 5м , 3 )
${\begin{bmatrix}0&3\\3&0\end{bmatrix}}$	Нет графиков	Просто G ( 2м , 3 )

Ссылки

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

[1] Коксетер, HSM (1950), «Самодвойственные конфигурации и регулярные графы», Бюллетень Американского математического общества , 56 (5): 413–455, doi : 10.1090/S0002-9904-1950-09407-5 .

[2] Уоткинс, Марк Э. (1969), «Теорема о раскрасках Тейта с применением к обобщенным графам Петерсена», Journal of Combinatorial Theory , 6 (2): 152–164, doi : 10.1016/S0021-9800(69)80116 -Х .

[3] Гросс, Джонатан Л.; Такер, Томас В. (1987), Топологическая теория графов , Нью-Йорк: Wiley . Пример 2.1.2, стр.58.

[4] Кэмпбелл, СР; Эллингем, Миннесота ; Ройл, Гордон Ф. (1993), «Характеристика хорошо покрытых кубических графов», Журнал комбинаторной математики и комбинаторных вычислений , 13 : 193–212, MR 1220613 .

[5] Фрухт, Р .; Грейвер, Дж. Э.; Уоткинс, М.Э. (1971), «Группы обобщенных графов Петерсена», Proceedings of the Cambridge Philosophical Society , 70 (2): 211–218, doi : 10.1017/S0305004100049811 .

[6] Альспах, Б.Р. (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, заархивировано из оригинала (PDF) 24 июля 2018 г. , получено 07 апреля 2017 г.

[10] Стеймле, Алиса; Стейтон, Уильям (2009), «Классы изоморфизма обобщенных графов Петерсена», Discrete Mathematics , 309 (1): 231–237, doi : 10.1016/j.disc.2007.12.074

[FH-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 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]