График Паппа - Pappus graph

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

в математический поле теория графов, то График Паппа это двудольный 3-обычный неориентированный граф с 18 вершинами и 27 ребрами, образованными как Граф Леви из Конфигурация Pappus.^[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.

• 

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

Рекомендации

1. Вайсштейн, Эрик В. «График Паппа». MathWorld.
2. Brouwer, A.E .; Коэн, А. М .; и Ноймайер А. Дистанционно регулярные графы. Нью-Йорк: Springer-Verlag, 1989.
3. Джессика Вольц, Инженерные линейные схемы с SAT. Магистерская работа, Тюбингенский университет, 2018 г.
4. Кагно, И. Н. (1947), "Графы Дезарга и Паппа и их группы", Американский журнал математики, Издательство Университета Джона Хопкинса, 69 (4): 859–863, Дои:10.2307/2371806, JSTOR  2371806
5. Ройл, Г. «Кубические симметричные графы (перепись Фостера)».
6. Кондер, М. и Добчани П. «Трехвалентные симметричные графы до 768 вершин». J. Combin. Математика. Комбинировать. Comput. 40, 41-63, 2002.