Граф Клебша
| Граф Клебша | |
|---|---|
 | |
| Назван в честь | Альфред Клебш |
| Вершины | 16 |
| Края | 40 |
| Радиус | 2 |
| Диаметр | 2 |
| Обхват | 4 |
| Автоморфизмы | 1920 |
| Хроматическое число | 4 [1] |
| Хроматический индекс | 5 |
| Толщина книги | 4 |
| Номер очереди | 3 |
| Характеристики | Сильно регулярный гамильтониан Граф Кэли Вершинно-транзитивный Край-транзитивный Дистанционно-транзитивный . |
| Таблица графиков и параметров | |
В математической области теории графов граф Клебша представляет собой один из двух дополнительных графов с 16 вершинами: 5- регулярный граф с 40 ребрами и 10-регулярный граф с 80 ребрами. Граф с 80 ребрами представляет собой граф половинного куба размерности 5 ; Зайдель (1968) назвал его именем графа Клебша. [2] из-за его связи с конфигурацией 16 линий на поверхности квартики, открытой в 1868 году немецким математиком Альфредом Клебшем . Вариант с 40 ребрами представляет собой свернутый граф-куб размерности 5 ; он также известен как график Гринвуда-Глисона в честь работы Роберта Э. Гринвуда и Эндрю М. Глисона ( 1955 ), которые использовали его для оценки числа Рамсея R (3,3,3) = 17. [3] [4] [5]
Строительство [ править ]
размерности 5 Граф свернутого куба (5-регулярный граф Клебша) может быть построен путем добавления ребер между противоположными парами вершин в 4-мерном графе гиперкуба. (В n -мерном гиперкубе пара вершин является противоположной, если кратчайший путь между ними имеет n ребер.) Альтернативно, его можно сформировать из 5-мерного графа гиперкуба, идентифицируя вместе (или сжимая) каждую противоположную пару вершин. .
Другая конструкция, приводящая к тому же графу, состоит в том, чтобы создать вершину для каждого элемента конечного поля GF(16) и соединить две вершины ребром всякий раз, когда разница между соответствующими двумя элементами поля представляет собой идеальный куб . [6]
размерности 5 Граф половинчатого куба (10-регулярный граф Клебша) является дополнением 5-регулярного графа. Его также можно построить из вершин 5-мерного гиперкуба путем соединения пар вершин, расстояние Хэмминга которых равно двум. Эта конструкция является примером конструкции графов Франкля–Рёдля . Он создает два подмножества по 16 вершин, которые не связаны друг с другом; оба этих полуквадрата гиперкуба изоморфны 10-регулярному графу Клебша. Две копии 5-регулярного графа Клебша можно получить таким же образом из 5-мерного гиперкуба, соединив пары вершин, расстояние Хэмминга которых равно четырем.
Свойства [ править ]
5-регулярный граф Клебша — это сильно регулярный граф степени 5 с параметрами . [7] [8] Поэтому его дополнение, 10-регулярный граф Клебша, также является сильно регулярным графом: [1] [4] с параметрами .
5-регулярный граф Клебша является гамильтоновым , непланарным и неэйлеровым . Он также является одновременно 5- вершинно-связным и 5- реберно-связным . Подграф , индуцированный десятью несоседями любой вершины в этом графе, образует изоморфную копию графа Петерсена .
Имеет толщину книги 4 и номер очереди 3. [9]
Ребра полного графа K 16 можно разбить на три непересекающиеся копии 5-регулярного графа Клебша. Поскольку граф Клебша является графом без треугольников , это показывает, что существует трехраскраска ребер K 16 без треугольников ; то есть, чтобы число Рамсея R (3,3,3), описывающее минимальное количество вершин в полном графе без трехраскраски без треугольников, было не менее 17. Гринвуд и Глисон (1955) использовали эту конструкцию как часть их доказательство того, что R (3,3,3) = 17. [5] [10]
5-регулярный граф Клебша можно раскрасить в четыре цвета, но не в три: его наибольшее независимое множество имеет пять вершин, чего недостаточно для разделения графа на три независимых цветовых класса. Он содержит в качестве индуцированного подграфа граф Грётча , наименьший четырёххроматический граф без треугольников , и каждый четырёххроматический индуцированный подграф графа Клебша является суперграфом графа Грётча. Более строго: каждый четыреххроматический граф без треугольников и без индуцированных путей длиной шесть или более является индуцированным подграфом графа Клебша и индуцированным суперграфом графа Грётча. [11]
5-регулярный граф Клебша — это граф Келлера размерности два, входящий в семейство графов, используемых для поиска мозаики многомерных евклидовых пространств гиперкубами , никакие два из которых не пересекаются лицом к лицу.
5-регулярный граф Клебша можно вложить как регулярное отображение в ориентируемое многообразие рода 5, образуя пятиугольные грани; и в неориентируемой поверхности рода 6, образующей тетрагональные грани.
Алгебраические свойства [ править ]
Характеристический полином 5-регулярного графа Клебша равен . Поскольку этот полином можно полностью разложить на линейные члены с целыми коэффициентами, граф Клебша является интегральным графом : его спектр полностью состоит из целых чисел. [4] Граф Клебша — единственный граф с этим характеристическим полиномом, что делает его графом, определяемым его спектром.
5-регулярный граф Клебша — это граф Кэли с группой автоморфизмов порядка 1920, изоморфный группе Коксетера. . Как граф Кэли, его группа автоморфизмов действует транзитивно на его вершинах, что делает его вершинно-транзитивным . Фактически, он транзитивен по дуге , следовательно, транзитивен по ребру и транзитивен по расстоянию . Он также связно-однороден , что означает, что каждый изоморфизм между двумя связными индуцированными подграфами может быть расширен до автоморфизма всего графа.
Галерея [ править ]
Граф Клебша является гамильтоновым .
Ахроматическое число графа Клебша равно 8.
Хроматическое число графа Клебша равно 4.
Хроматический индекс графа Клебша равен 5.
Построение графа Клебша по графу гиперкуба .
Ссылки [ править ]
- ↑ Перейти обратно: Перейти обратно: а б Вайсштейн, Эрик В. «График Клебша» . Из MathWorld — веб-ресурса Wolfram . Проверено 13 августа 2009 г.
- ^ Дж. Дж. Зайдель, Сильно регулярные графы с (-1,1,0) матрицей смежности, имеющей собственное значение 3, Lin. Алг. Прил. 1 (1968) 281-298.
- ^ Клебш, А. (1868), «О поверхностях четвертого порядка, имеющих двойную кривую второй степени», Журнал чистой и прикладной математики , 69 : 142–184 .
- ↑ Перейти обратно: Перейти обратно: а б с «График Клебша на домашней странице Билла Черовицо» (PDF) . Архивировано из оригинала (PDF) 29 октября 2013 г. Проверено 21 мая 2011 г.
- ↑ Перейти обратно: Перейти обратно: а б Гринвуд, RE; Глисон, AM (1955), «Комбинаторные отношения и хроматические графы», Canadian Journal of Mathematics , 7 : 1–7, doi : 10.4153/CJM-1955-001-4 , MR 0067467 .
- ^ Де Клерк, Франк (1997). «Конструкции и характеристики (полу)частичных геометрий» . Летняя школа по конечной геометрии. п. 6.
- ^ Годсил, компакт-диск (1995). «Проблемы алгебраической комбинаторики» (PDF) . Электронный журнал комбинаторики . 2 :3. дои : 10,37236/1224 . Проверено 13 августа 2009 г.
- ^ Питер Дж. Кэмерон Сильно регулярные графики на DesignTheory.org, 2001 г.
- ^ Джессика Вольц, Разработка линейных макетов с помощью SAT . Магистерская диссертация, Тюбингенский университет, 2018 г.
- ^ Сан, Хьюго С.; Коэн, Мэн (1984), «Простое доказательство оценки Гринвуда-Глисона числа Рэмси R (3,3,3)» (PDF) , The Fibonacci Quarterly , 22 (3): 235–238, MR 0765316 .
- ^ Рандерат, Берт; Ширмейер, Инго; Тьюс, Мейке (2002), «Три раскраски и запрещенные подграфы. II. Полиномиальные алгоритмы», Discrete Mathematics , 251 (1–3): 137–153, doi : 10.1016/S0012-365X(01)00335-1 , MR 1904597 .