В теории графов , то обобщенные графы Петерсена представляют собой семейство кубических графов , образованных путем соединения вершин правильного многоугольника с соответствующими вершинами звезды многоугольника . Они включают граф Петерсена и обобщают один из способов построения графа Петерсена. Семейство обобщенных графов Петерсена было введено в 1950 году HSM Coxeter [1] и получило свое название в 1969 году от Марка Уоткинса. [2]
Определение и обозначения
В обозначениях Уоткинса G ( n , k ) - граф с множеством вершин
и набор кромок
где индексы следует читать по модулю 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-вершинно-связными и хорошо покрытыми (что означает, что все графы их максимальных независимых множеств имеют одинаковый размер). [4]
Характеристики
Это семейство графов обладает рядом интересных свойств. Например:
- G ( n , k ) является вершинно-транзитивным (это означает, что он имеет симметрии, которые переводят любую вершину в любую другую вершину) тогда и только тогда, когда ( n , k ) = (10, 2) или k 2 ≡ ± 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 2 ≡ 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 ) тогда и только тогда, когда kl ≡ ± 1 (mod n ). [10]
Обхват
Обхват G ( n , k ) не менее 3 и не более 8, в частности: [11]
Таблица с точными значениями обхвата:
Условие Обхват 3 4 5 6 7 иначе 8
Хроматическое число и хроматический индекс
Будучи регулярными , согласно теореме Брукса их хроматическое число не может быть больше их степени . Обобщенные графы Петерсена кубические, поэтому их хроматическое число может быть 2 или 3. Точнее:
Где обозначает логическое И , алогическое ИЛИ . Например, хроматическое число равно 3.
3-раскраска графа Петерсена или
2-раскраска графа Дезарга или
3-раскраска графа Дюрера или
Граф Петерсена , будучи снарком , имеет хроматический индекс 4. Все остальные обобщенные графы Петерсена имеют хроматический индекс 3. [12]
Обобщенный граф Петерсена G (9, 2) - один из немногих графов, которые, как известно, имеют только одну 3-реберную раскраску . [13]
4-краевая раскраска графа Петерсена или
Трехреберная раскраска графа Дюрера или
Трехреберная раскраска додекаэдра или
Трехреберная раскраска графа Дезарга или
3-краевая раскраска графа Науру или
Граф Петерсена сам по себе является единственным обобщенным графом Петерсена, не раскрашиваемым по ребрам . [14]
Рекомендации
- ^ Косетер, HSM (1950), "Автодуальные конфигурации и регулярные графы", Бюллетень Американского математического общества , 56 (5): 413-455, DOI : 10,1090 / S0002-9904-1950-09407-5.
- ^ Уоткинс, Марк Э. (1969), «Теорема о раскраске Тейта с приложением к обобщенным графам Петерсена», Журнал комбинаторной теории , 6 (2): 152–164, DOI : 10.1016 / S0021-9800 (69) 80116 -ИКС.
- ^ Гросс, Джонатан Л .; Такер, Томас В. (1987), Теория топологических графов , Нью-Йорк: Wiley. Пример 2.1.2, стр.58.
- ^ Кэмпбелл, SR; Эллингем, Миннесота ; Ройл, Гордон Ф. (1993), "Характеристика хорошо покрытых кубических графов", Журнал комбинаторной математики и комбинаторных вычислений , 13 : 193–212, MR 1220613.
- ^ Frucht, R .; Graver, JE; Watkins, ME (1971), "Группы обобщенных графов Петерсена", Труды Кембриджского философского общества , 70 (2): 211-218, DOI : 10,1017 / S0305004100049811.
- ^ Alspach, BR (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.
- ^ Штаймле, Алиса; Staton, Уильям (2009), "Классы изоморфизма обобщенных графов Петерсена", Дискретная математика , 309 (1): 231-237, DOI : 10.1016 / j.disc.2007.12.074
- ^ Ферреро, Даниэла; Hanusch, Сара (2014), "компонент связности обобщенных графов Петерсена" (PDF) , Международный журнал вычислительной математики , 91 (9): 1940-1963, DOI : 10,1080 / 00207160.2013.878023 , ISSN 0020-7160 , архивируются с оригинал (PDF) от 20.10.2018 , дата обращения 20.10.2018
- ^ Кастанья, Франк; Принса, Герт Калеб Эрнст (1972), "Каждый обобщенный Петерсен граф имеет Tait окраски", Тихоокеанский журнал математики , 40 (1): 53-58, DOI : 10,2140 / pjm.1972.40.53 , ISSN 0030-8730 , М.Р. 0304223 , Zbl 0236.05106
- ^ Боллобаш, Бела (2004), Экстремальная теория графов , Дувр, с. 233. Перепечатка издания Academic Press 1978 года.
- ^ Кастанья, Франк; Принс, Герт (1972), «Каждый обобщенный граф Петерсена имеет окраску тайта », Pacific Journal of Mathematics , 40 : 53–58, doi : 10.2140 / pjm.1972.40.53.