График Паппа

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

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

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

Граф Паппа имеет хроматический многочлен , равный: .${\ displaystyle (x-1) x (x ^ {16} -26x ^ ​​{15} + 325x ^ {14} -2600x ^ {13} + 14950x ^ {12} -65762x ^ {11} +}$${\displaystyle 229852x^{10}-653966x^{9}+1537363x^{8}-3008720x^{7}+4904386x^{6}-}$${\displaystyle 6609926x^{5}+7238770x^{4}-6236975x^{3}+3989074x^{2}-1690406x+356509)}$

Название «граф Паппа» также использовалось для обозначения связанного графа с девятью вершинами ^[4] с вершиной для каждой точки конфигурации Паппа и ребром для каждой пары точек на одной прямой; этот граф с девятью вершинами является 6-регулярным, является дополнительным графом объединения трех непересекающихся треугольных графов и является полным трехдольным графом K _3,3,3 . Первый граф Паппа может быть вложен в тор, чтобы образовать само- дуальное регулярное отображение Петри с девятью шестиугольными гранями; второй, чтобы сформировать правильную карту с 18 треугольными гранями. Два обычных тороидальных отображения двойственны друг другу.

Алгебраические свойства [ править ]

Группа автоморфизмов графа Паппа - это группа порядка 216. Она действует транзитивно на вершинах, на ребрах и на дугах графа. Следовательно, граф Паппа является симметричным графом . У него есть автоморфизмы, которые переводят любую вершину в любую другую вершину и любое ребро в любое другое ребро. Согласно переписи населения Фостера , граф Паппа, обозначенный как F018A, является единственным кубическим симметричным графом с 18 вершинами. ^{[5] [6]}

Характеристический полином графа хохолка является . Это единственный граф с таким характеристическим многочленом, что делает его графом, определяемым его спектром.${\displaystyle (x-3)x^{4}(x+3)(x^{2}-3)^{6}}$

Галерея [ править ]

• 

  График Паппа раскрашен, чтобы выделить различные циклы.

• 

  Хроматической индекс графа хохолка равен 3.

• Хроматического числа графа хохолка 2.

• Граф Паппа, вложенный в тор, как регулярное отображение с девятью шестиугольными гранями.

• Граф Паппа и связанное с ним отображение, вложенное в тор.

Ссылки [ править ]