В математической области теории графов , то графы Ellingham-Horton два 3- регулярные графы на 54 и 78 вершин: The Ellingham-Хортон 54-граф и Ellingham-Хортон 78-граф . [1] Они названы в честь Джозефа Д. Хортона и Марка Н. Эллингема , их первооткрывателей. Эти два графа предоставляют контрпримеры к гипотезе У. Т. Татта о том, что каждый кубический 3-связный двудольный граф является гамильтоновым . [2] книга толщиной от Ellingham-Horton 54-графаи 78-граф Эллингема-Хортона равен 3, а номер очереди - 2. [3]
Графы Эллингема – Хортона | |
---|---|
Названный в честь | Джозеф Хортон и Марк Эллингем |
Вершины | 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 (оба) |
Характеристики | Кубическая (обе) Двудольные (обе) Правильные (обе) |
Таблица графиков и параметров |
Первым контрпримером к гипотезе Тутте был граф Хортона , опубликованный Bondy & Murty (1976) . [4] После графа Хортона был найден ряд меньших контрпримеров к гипотезе Тутте. Среди них 92-вершинный граф Хортона (1982) , [5] 78-вершинный граф Оуэнса (1983) , [6] и два графа Эллингема – Хортона.
Первый граф Эллингема – Хортона был опубликован Эллингемом (1981) и имеет порядок 78. [7] В то время это был наименьший известный контрпример к гипотезе Тутте. Второй граф Эллингема – Хортона был опубликован Ellingham & Horton (1983) и имеет порядок 54. [8] В 1989 году был открыт граф Жоржа, самый маленький из известных в настоящее время негамильтоновых 3-связных кубических двудольных графов, содержащий 50 вершины. [9]
Галерея
Хроматическим числом от Ellingham-Horton 54-графа 2.
Хроматической индекс из Ellingham-Horton 54-графа 3.
Хроматическим числом от Ellingham-Horton 78-графа 2.
Хроматической индекс из Ellingham-Horton 78-графа 3.
Рекомендации
- ^ Вайсштейн, Эрик В. «Гипотеза Тутте» . MathWorld .
- ^ Тутта, WT (1971), "О 2-факторах бикубических графов", дискретная математика , 1 (2): 203-208, DOI : 10.1016 / 0012-365X (71) 90027-6.
- ^ Джессика Wolz, Инженерная Линейные Макеты с SAT. Магистерская работа, Тюбингенский университет, 2018 г.
- ^ Бонди, JA ; Мурти, USR (1976), Теория графов с приложениями , Нью-Йорк: Северная Голландия, стр. 240 , ISBN 0-444-19451-7
- ^ Хортон, Дж. Д. (1982), "О двухфакторах двудольных регулярных графов", Дискретная математика , 41 (1): 35–41, DOI : 10.1016 / 0012-365X (82) 90079-6.
- ^ Оуэнс, PJ (1983), "двудольные кубические графы и затрудненное показатель", дискретная математика , 44 (3): 327-330, DOI : 10.1016 / 0012-365X (83) 90201-7.
- ^ Эллингем, М.Н. (1981), Негамильтоновы 3-связные кубически-разделенные графы , Исследовательский отчет 28, Мельбурн: Департамент математики, Univ. Мельбурн.
- ^ Эллингем, Миннесота; Хортон, Дж. Д. (1983), « Негамильтоновы трехсвязные кубические двудольные графы», Журнал комбинаторной теории, серия B , 34 (3): 350–353, DOI : 10.1016 / 0095-8956 (83) 90046-1.
- ^ Жорж, JP (1989), «Негамильтоновы бикубические графы», Журнал комбинаторной теории, серия B , 46 (1): 121–124, DOI : 10.1016 / 0095-8956 (89) 90012-9.