В математической области теории графов , то граф Клебша является одним из двух дополнительных графов на 16 вершинах, 5- регулярного графа с 40 ребер и 10-регулярного графа с 80 ребрами. 80-реберный граф - это разрезанный пополам кубический граф размерности 5 ; Зайдель (1968) [2] назвал его графом Клебша из-за его связи с конфигурацией из 16 линий на поверхности четвертой степени, открытой в 1868 году немецким математиком Альфредом Клебшем . Вариант с 40 ребрами - это свернутый куб размерности 5 ; он также известен как граф Гринвуда – Глисонапосле работы Роберта Э. Гринвуда и Эндрю М. Глисона ( 1955 ), которые использовали его для вычисления числа Рамси R (3,3,3) = 17. [3] [4] [5]
Граф Клебша | |
---|---|
Названный в честь | Альфред Клебш |
Вершины | 16 |
Края | 40 |
Радиус | 2 |
Диаметр | 2 |
Обхват | 4 |
Автоморфизмы | 1920 г. |
Хроматическое число | 4 [1] |
Хроматический индекс | 5 |
Толщина книги | 4 |
Номер очереди | 3 |
Характеристики | Сильно регулярный гамильтонов граф Кэли. Вершинно-транзитивный, реберный транзитивный, дистанционно-транзитивный . |
Таблица графиков и параметров |
Строительство
Граф свернутого куба размерности 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-регулярный граф Клебша является Keller граф размерности два, часть семейства графов используются для поиска замощений многомерных евклидовых пространств на гиперкуб не два из которых встречается лицом к лицу.
5-регулярный граф Клебша может быть вложен как регулярное отображение в ориентируемое многообразие рода 5, образуя пятиугольные грани; и в неориентируемой поверхности рода 6, образующей тетрагональные грани.
Алгебраические свойства
Характеристический полином из 5-регулярного графа Клебша. Поскольку этот многочлен может быть полностью разложен на линейные члены с целыми коэффициентами, граф Клебша является интегральным графом : его спектр полностью состоит из целых чисел. [4] Граф Клебша - единственный граф с этим характеристическим полиномом, что делает его графом, определяемым его спектром.
5-регулярный граф Клебша - это граф Кэли с группой автоморфизмов порядка 1920, изоморфный группе Кокстера. . В графе Кэли, его группа автоморфизмов действует транзитивно на его вершинах, что делает его вершина транзитивным . Фактически, это дугово-транзитивное , следовательно, реберное и дистанционно-транзитивное . Он также является связно-однородным , что означает, что любой изоморфизм между двумя связными индуцированными подграфами может быть расширен до автоморфизма всего графа.
Галерея
Граф Клебша гамильтонов .
Ахроматические число графа Клебша 8.
Хроматического числа графа Клебша равно 4.
Хроматической индекс графа Клебша 5.
Построение графа Клебша из графа гиперкуба .
Рекомендации
- ^ a b Вайсштейн, Эрик В. "График Клебша" . Материал из MathWorld - веб-ресурса Wolfram . Проверено 13 августа 2009 .
- ^ JJ Зайдель, Сильно регулярные графы с (−1,1,0) матрицей смежности, имеющей собственное значение 3, Lin. Alg. Прил. 1 (1968) 281-298.
- ^ Клебш, А. (1868), «Ueber die Flächen vierter Ordnung, welche eine Doppelcurve zweiten Grades besitzen», Journal für die reine und angewandte Mathematik , 69 : 142–184.
- ^ a b c График Клебша на домашней странице Билла Черовицо
- ^ а б Гринвуд, RE; Глисон, AM (1955), "Комбинаторные отношения и хроматических графов", Canadian Journal математики , 7 : 1-7, DOI : 10,4153 / CJM-1955-001-4 , MR 0067467.
- ^ Де Клерк, Франк (1997). «Построения и характеристики (полу) частичных геометрий» . Летняя школа по конечным геометриям. п. 6.
- ^ Годсил, компакт-диск (1995). «Проблемы алгебраической комбинаторики» (PDF) . Электронный журнал комбинаторики . 2 : 3 . Проверено 13 августа 2009 .
- ^ Питер Дж. Кэмерон Сильно регулярные графы на DesignTheory.org, 2001
- ^ Джессика Wolz, Инженерная Линейные Макеты с SAT . Магистерская работа, Тюбингенский университет, 2018 г.
- ^ Sun, Hugo S .; Коэн, ME (1984), "Простое доказательство оценки Гринвуда – Глисона числа Рамсея R (3,3,3)" (PDF) , The Fibonacci Quarterly , 22 (3): 235–238, MR 0765316.
- ^ Рандерат, Берт; Ширмейер, Инго; Tewes, MeiKe (2002), "Три-colourability и запрещенные подграфы II полиномиальные алгоритмы..", Дискретной математики , 251 (1-3): 137-153, DOI : 10.1016 / S0012-365X (01) 00335-1 , М.Р. 1904597.