В теории графов графом Паппа называется двудольный 3-регулярный неориентированный граф с 18 вершинами и 27 рёбрами, являющийся графом Леви конфигурации Паппа. Он назван в честь Паппа Александрийского, математика Древней Греции, который верил, что доказал «теорему о шестиугольнике», в которой описывал конфигурацию Паппа. Все кубические дистанционно-регулярные графы известны. Граф Паппа — один из тринадцати таких графовBrouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance — Regular Graphs. New York: Springer—Verlag, 1989..

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

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

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

Алгебраические свойства Группа автоморфизмов графа Паппа — это группа с порядком 216. Она действует транзитивно на вершины и рёбра графа. Таким образом, граф Паппа является симметричным. У него есть автоморфизмы, переводящие любую вершину в любую другую и любое ребро в любое другое ребро. В списке Фостера граф Папа обозначен как F018A и является единственным кубическим симметричным графом с 18 вершинамиRoyle, G. «Cubic Symmetric Graphs (The Foster Census).» and Dobcsányi, P. «Trivalent Symmetric Graphs Up to 768 Vertices.» J. Combin. Math. Combin. Comput. 40, 41—63, 2002..

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

Галерея

Примечания

Категория:Регулярные графы Категория:Графы, имеющие собственные названия Категория:Графы с хроматическим числом 2 Категория:Двудольные графы