Граф Паппуса
| Граф Паппуса | |
|---|---|
 Граф Паппуса. | |
| Назван в честь | Папп Александрийский |
| Вершины | 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]
Граф Паппуса имеет хроматический полином, равный:
Название «граф Паппуса» также использовалось для обозначения связанного графа с девятью вершинами. [4] с вершиной для каждой точки конфигурации Паппуса и ребром для каждой пары точек на одной прямой; этот граф с девятью вершинами является 6-регулярным, является графом дополнений объединения трех непересекающихся треугольных графов и является полным трехдольным графом K 3,3,3 . Первый граф Паппуса можно встроить в тор, чтобы сформировать двойственное Петри регулярное отображение с девятью шестиугольными гранями; второй — сформировать правильную карту с 18 треугольными гранями. Два обычных тороидальных отображения двойственны друг другу.
Алгебраические свойства [ править ]
Группа автоморфизмов графа Паппуса — это группа порядка 216. Она действует транзитивно на вершинах, ребрах и дугах графа. Следовательно, граф Паппуса является симметричным графом . Он имеет автоморфизмы, которые переводят любую вершину в любую другую вершину и любое ребро в любое другое ребро. Согласно переписи Фостера , граф Паппуса, обозначенный как F018A, является единственным кубически-симметричным графом с 18 вершинами. [5] [6]
Характеристический полином графа Паппуса равен . Это единственный граф с этим характеристическим полиномом, что делает его графом, определяемым его спектром.
Галерея [ править ]
График Паппуса раскрашен для выделения различных циклов.
Хроматический индекс графа Паппуса равен 3.
Хроматическое число графа Паппуса равно 2.
Граф Паппуса, встроенный в тор, представляет собой правильную карту с девятью шестиугольными гранями.
Граф Паппуса и связанная с ним карта, встроенная в тор.
Ссылки [ править ]
- ^ Вайсштейн, Эрик В. «График Паппуса» . Математический мир .
- ^ Брауэр, А.Э.; Коэн, AM; и Ноймайер А. Дистанционно-регулярные графы. Нью-Йорк: Springer-Verlag, 1989.
- ^ Джессика Вольц, Разработка линейных макетов с помощью SAT. Магистерская диссертация, Тюбингенский университет, 2018 г.
- ^ Каньо, Индиана (1947), «Графы Дезарга и Паппа и их группы», American Journal of Mathematics , 69 (4), The Johns Hopkins University Press: 859–863, doi : 10.2307/2371806 , JSTOR 2371806
- ^ Ройл, Г. «Кубические симметричные графы (перепись Фостера)».
- ^ Кондер М. и Добчани П. «Трехвалентные симметричные графы до 768 вершин». Дж. Комбин. Математика. Комбинировать. Вычислить. 40, 41–63, 2002.