Граф Паппа
| Граф Паппа | |
|---|---|
 | |
| Назван в честь | Папп Александрийский |
| Вершин | 18 |
| Рёбер | 27 |
| Радиус | 4 |
| Диаметр | 4 |
| Обхват | 6 |
| Автоморфизмы | 216 |
| Хроматическое число | 2 |
| Хроматический индекс | 3 |
| Свойства |
двудольный |
В теории графов графом Паппа называется двудольный 3-регулярный неориентированный граф с 18 вершинами и 27 рёбрами, являющийся графом Леви конфигурации Паппа[1]. Он назван в честь Паппа Александрийского, математика Древней Греции, который верил, что доказал «теорему о шестиугольнике», в которой описывал конфигурацию Паппа. Все кубические дистанционно-регулярные графы известны. Граф Паппа — один из тринадцати таких графов[2].
Число прямолинейных скрещиваний графа Паппа равно 5, и этот граф является наименьшим кубическим графом с таким числом скрещиваний (последовательность A110507 в OEIS). Граф имеет обхват 6, диаметр 4, радиус 4, хроматическое число 2, хроматический индекс 3, а также является и вершинно 3-связным, и рёберно 3-связным.
Хроматический многочлен графа Паппа равен [math]\displaystyle{ (x-1)x(x^{16}-26x^{15}+325x^{14}-2600x^{13}+14950x^{12}-65762x^{11}+ }[/math][math]\displaystyle{ 229852x^{10}-653966x^9+1537363x^8-3008720x^7+4904386x^6- }[/math][math]\displaystyle{ 6609926x^5+7238770x^4-6236975x^3+3989074x^2-1690406x+356509) }[/math].
Имя «граф Паппа» используется также для близкого графа с девятью вершинами[3], по вершине для каждой точки конфигурации Паппа с рёбрами для каждой пары точек, находящихся на одной линии. Этот граф 6-регулярен и является дополнением объединения трёх не связанных друг с другом треугольных графов. Первый граф Паппа можно вложить в тор, получая при этом правильную карту[англ.] с девятью шестиугольными гранями. Второй граф образует при таком вложении правильную карту с 18 треугольными гранями.
Алгебраические свойства
Группа автоморфизмов графа Паппа — это группа с порядком 216. Она действует транзитивно на вершины и рёбра графа. Таким образом, граф Паппа является симметричным. У него есть автоморфизмы, переводящие любую вершину в любую другую и любое ребро в любое другое ребро. В списке Фостера граф Папа обозначен как F018A и является единственным кубическим симметричным графом с 18 вершинами[4][5].
Характеристический многочлен графа Паппа равен [math]\displaystyle{ (x-3) x^4 (x+3) (x^2-3)^6 }[/math]. Это единственный граф с таким характеристическим полиномом, так что в данном случае граф определяется своим спектром.
Галерея
-
Граф Паппа, раскрашенный для выделения различных циклов.
-
хроматический индекс графа Паппа равен 3.
-
Хроматическое число графа Паппа равно 2.
Примечания
- ↑ Weisstein, Eric W. Pappus Graph (англ.) на сайте Wolfram MathWorld.
- ↑ Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance — Regular Graphs. New York: Springer—Verlag, 1989.
- ↑ 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.
- ↑ Royle, G. «Cubic Symmetric Graphs (The Foster Census).» Архивировано 20 июля 2008 года.
- ↑ Conder, M.[англ.] and Dobcsányi, P. «Trivalent Symmetric Graphs Up to 768 Vertices.» J. Combin. Math. Combin. Comput. 40, 41—63, 2002.
 | Для улучшения этой статьи желательно: |