Граф Паппа

В теории графов графом Паппа называется двудольный 3-регулярный неориентированный граф с 18 вершинами и 27 рёбрами, являющийся графом Леви конфигурации Паппа[1]. Он назван в честь Паппа Александрийского, математика Древней Греции, который верил, что доказал «теорему о шестиугольнике», в которой описывал конфигурацию Паппа. Все кубические дистанционно-регулярные графы известны. Граф Паппа — один из тринадцати таких графов[2].

Граф Паппа
Назван в честь Папп Александрийский
Вершин 18
Рёбер 27
Радиус 4
Диаметр 4
Обхват 6
Автоморфизмы 216
Хроматическое число 2
Хроматический индекс 3
Свойства

двудольный
симметричный
кубический
гамильтонов
дистанционно-транзитивен

дистанционно-регулярен
 Медиафайлы на Викискладе

Число прямолинейных скрещиваний графа Паппа равно 5, и этот граф является наименьшим кубическим графом с таким числом скрещиваний (последовательность A110507 в OEIS). Граф имеет обхват 6, диаметр 4, радиус 4, хроматическое число 2, хроматический индекс 3, а также является и вершинно 3-связным, и рёберно 3-связным.

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

Имя «граф Паппа» используется также для близкого графа с девятью вершинами[3], по вершине для каждой точки конфигурации Паппа с рёбрами для каждой пары точек, находящихся на одной линии. Этот граф 6-регулярен и является дополнением объединения трёх не связанных друг с другом треугольных графов. Первый граф Паппа можно вложить в тор, получая при этом правильную карту с девятью шестиугольными гранями. Второй граф образует при таком вложении правильную карту с 18 треугольными гранями.

Алгебраические свойства

Группа автоморфизмов графа Паппа — это группа с порядком 216. Она действует транзитивно на вершины и рёбра графа. Таким образом, граф Паппа является симметричным. У него есть автоморфизмы, переводящие любую вершину в любую другую и любое ребро в любое другое ребро. В списке Фостера граф Папа обозначен как F018A и является единственным кубическим симметричным графом с 18 вершинами[4][5].

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

Галерея

Примечания
  1. Weisstein, Eric W. Pappus Graph (англ.) на сайте Wolfram MathWorld.
  2. Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance — Regular Graphs. New York: Springer—Verlag, 1989.
  3. I. N. Kagno. Desargues' and Pappus' graphs and their groups. — American Journal of Mathematics. — The Johns Hopkins University Press, 1947. — Т. 69. — С. 859—863. — doi:10.2307/2371806.
  4. Royle, G. «Cubic Symmetric Graphs (The Foster Census).» Архивировано 20 июля 2008 года.
  5. Conder, M. and Dobcsányi, P. «Trivalent Symmetric Graphs Up to 768 Vertices.» J. Combin. Math. Combin. Comput. 40, 41—63, 2002.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.