Граф Эллингхэма–Хортона
| Графы Эллингхэма–Хортона | |
|---|---|
 54-график Эллингхэма–Хортона. | |
| Назван в честь | Джозеф Хортон и Марк Эллингем |
| Вершины | 54 (54-график) 78 (78-график) |
| Края | 81 (54-график) 117 (78-график) |
| Радиус | 9 (54-график) 7 (78-график) |
| Диаметр | 10 (54-график) 13 (78-график) |
| Обхват | 6 (оба) |
| Автоморфизмы | 32 (54-график) 16 (78-график) |
| Хроматическое число | 2 (оба) |
| Хроматический индекс | 3 (оба) |
| Толщина книги | 3 (оба) |
| Номер очереди | 2 (оба) |
| Характеристики | Кубический (оба) Двудольный (оба) Правильный (оба) |
| Таблица графиков и параметров | |
В математической области теории графов графы Эллингема –Хортона — это два 3- регулярных графа с 54 и 78 вершинами: 54-граф Эллингема–Хортона и 78-граф Эллингема–Хортона . [1] Они названы в честь Джозефа Д. Хортона и Марка Н. Эллингема , их первооткрывателей. Эти два графа являются контрпримерами к гипотезе У. Т. Тутта о том , что каждый кубический 3-связный двудольный граф является гамильтоновым . [2] Толщина книги 54-графа Эллингема–Хортона и 78 -графа Эллингема–Хортона равна 3, а число очередей равно 2. [3]
Первым контрпримером к гипотезе Тутта был граф Хортона , опубликованный Бонди и Мурти (1976). [4] После графа Хортона было найдено несколько меньших контрпримеров к гипотезе Тутта. Среди них — граф с 92 вершинами Хортона (1982), [5] граф с 78 вершинами Оуэнса (1983), [6] и два графа Эллингхэма–Хортона.
Первый граф Эллингхэма–Хортона был опубликован Эллингхэмом (1981) и имеет порядок 78. [7] В то время это был наименьший известный контрпример к гипотезе Тутта. Второй граф Эллингхэма–Хортона был опубликован Эллингхэмом и Хортоном (1983) и имеет порядок 54. [8] В 1989 году был обнаружен граф Жоржа, наименьший известный в настоящее время негамильтонов 3-связный кубический двудольный граф, содержащий 50 вершин. [9]
Галерея
- Хроматическое число 54-графа Эллингема–Хортона равно 2.
- Хроматический индекс 54-графа Эллингхэма–Хортона равен 3.
- Хроматическое число 78-графа Эллингхэма–Хортона равно 2.
- Хроматический индекс 78-графа Эллингхэма–Хортона равен 3.
Ссылки
- ^ Вайсштейн, Эрик В. «Тутте-гипотеза». Математический мир .
- ^ Tutte, WT (1971), «О 2-факторах бикубических графов», Discrete Mathematics , 1 (2): 203–208 , doi : 10.1016/0012-365X(71)90027-6.
- ^ Джессика Вольц, Разработка линейных макетов с помощью SAT. Магистерская диссертация, Тюбингенский университет, 2018 г.
- ^ Бонди, JA ; Мурти, USR (1976), Теория графов с приложениями, Нью-Йорк: Северная Голландия, стр. 240, ISBN 0-444-19451-7
- ^ Хортон, Дж. Д. (1982), «О двухфакторных двудольных регулярных графах», Дискретная математика , 41 (1): 35– 41, doi : 10.1016/0012-365X(82)90079-6.
- ^ Оуэнс, П.Дж. (1983), «Двудольные кубические графы и показатель краткости», Дискретная математика , 44 (3): 327– 330, doi :10.1016/0012-365X(83)90201-7.
- ^ Эллингем, МН (1981), Негамильтоновы 3-связные кубические дольные графы , Исследовательский отчет 28, Мельбурн: Кафедра математики, Мельбурнский ун-т..
- ^ Эллингем, МН; Хортон, ДжД (1983), «Негамильтоновы 3-связные кубические двудольные графы», Журнал комбинаторной теории, Серия B , 34 (3): 350–353 , doi : 10.1016/0095-8956(83)90046-1.
- ^ Жорж, Дж. П. (1989), «Негамильтоновы бикубические графы», Журнал комбинаторной теории, Серия B , 46 (1): 121– 124, doi :10.1016/0095-8956(89)90012-9.
