Граф Вагнера

Кубический граф с 8 вершинами и 12 ребрами

В математической области теории графов граф Вагнера — это 3- регулярный граф с 8 вершинами и 12 ребрами. ^[1] Это граф лестницы Мёбиуса с 8 вершинами .

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

Как лестница Мёбиуса, граф Вагнера непланарен , но имеет пересечение номер один, что делает его графом вершин . Он может быть вложен без пересечений в тор или проективную плоскость , поэтому он также является тороидальным графом . Он имеет обхват 4, диаметр 2, радиус 2, хроматическое число 3, хроматический индекс 3 и является как 3- вершинно-связным , так и 3- рёберно-связным .

Граф Вагнера имеет 392 остовных дерева ; он и полный двудольный граф K _3,3 имеют наибольшее количество остовных деревьев среди всех кубических графов с тем же числом вершин. ^[2]

Граф Вагнера является вершинно-транзитивным графом , но не является рёберно-транзитивным . Его полная группа автоморфизмов изоморфна диэдральной группе D ₈ порядка 16, группе симметрий восьмиугольника , включая как вращения, так и отражения.

Характеристический многочлен графа Вагнера равен

${\displaystyle (x-3)(x-1)^{2}(x+1)(x^{2}+2x-1)^{2}.}$

Это единственный граф с таким характеристическим многочленом, что делает его графом, определяемым его спектром .

Граф Вагнера не содержит треугольников и имеет число независимости три, что обеспечивает половину доказательства того, что число Рамсея R (3,4) (наименьшее число n, такое, что любой граф с n вершинами содержит либо треугольник, либо независимое множество из четырех вершин) равно 9. ^[3]

Графические несовершеннолетние

Лестницы Мёбиуса играют важную роль в теории миноров графов . Самым ранним результатом этого типа является теорема Клауса Вагнера 1937 года (часть кластера результатов, известных как теорема Вагнера ) о том, что графы без миноров K ₅ могут быть образованы с помощью операций суммы клик для объединения планарных графов и лестницы Мёбиуса M ₈ . ^[4] По этой причине M ₈ называется графом Вагнера.

Граф Вагнера также является одним из четырех минимальных запрещенных миноров для графов с древовидной шириной не более трех (остальные три — это полный граф K ₅ , граф правильного октаэдра и граф пятиугольной призмы ) и одним из четырех минимальных запрещенных миноров для графов с ветвящейся шириной не более трех (остальные три — это K ₅ , граф октаэдра и граф куба ). ^{[5] [6]}

Строительство

Граф Вагнера является кубическим гамильтоновым графом и может быть определен с помощью нотации LCF [4] ⁸ . Это пример графа Андрашфаи , типа циркулянтного графа , в котором вершины могут быть расположены в цикле, и каждая вершина соединена с другими вершинами, позиции которых отличаются числом, равным 1 (mod 3). Он также изоморфен круговой клике K _8/3 .

Его можно изобразить в виде лестничного графа с четырьмя ступенями, зацикленными на топологической ленте Мёбиуса .

Галерея

• 
  Хроматическое число графа Вагнера равно 3.
• 
  Хроматический индекс графа Вагнера равен 3.
• 
  Граф Вагнера, нарисованный на ленте Мёбиуса.

Ссылки

1. Бонди, JA ; Мурти, USR (2007). Теория графов . Springer. стр. 275–276. ISBN 978-1-84628-969-9.
2. Якобсон, Дмитрий; Ривин, Игорь (1999). «О некоторых экстремальных задачах в теории графов». arXiv : math.CO/9907050 .
3. Сойфер, Александр (2008). Математическая раскраска . Springer-Verlag. стр. 245. ISBN 978-0-387-74640-1.
4. Вагнер, К. (1937). «Über eine Eigenschaft der ebenen Komplexe». Mathematische Annalen (на немецком языке). 114 (1): 570–590. дои : 10.1007/BF01594196. S2CID  123534907.
5. Бодлендер, Ханс Л. (1998). «Частичный k -дендрарий графов с ограниченной древовидной шириной». Теоретическая информатика . 209 (1–2): 1–45. doi :10.1016/S0304-3975(97)00228-4. hdl : 1874/18312 .
6. Бодлендер, Ханс Л.; Тиликос, Димитриос М. (1999). «Графы с шириной ветвей не более трех». Журнал алгоритмов . 32 (2): 167–194. doi :10.1006/jagm.1999.1011. hdl : 1874/2734 .