График Хортона

График Хортона
График Хортона
	График Хортона
Назван в честь	Джозеф Хортон
Вершины	96
Края	144
Радиус	10
Диаметр	10
Обхват	6
Автоморфизмы	96 ; ( Z /2 Z × Z /2 Z × S 4 )
Хроматическое число	2
Хроматический индекс	3
Толщина книги	3
Номер очереди	2
Характеристики	Кубический ; двусторонний
	Таблица графиков и параметров

В математической области теории графов граф Хортона или 96-граф Хортона представляет собой 3- регулярный граф с 96 вершинами и 144 ребрами, открытый Джозефом Хортоном. ^[1] Опубликованный Бонди и Мёрти в 1976 году, он представляет собой контрпример к гипотезе Тутта о том, что каждый кубический 3-связный двудольный граф является гамильтоновым . ^[2]^[3]

После графа Хортона был найден ряд меньших контрпримеров к гипотезе Тутте. Среди них граф с 92 вершинами Хортона, опубликованный в 1982 году, граф с 78 вершинами Оуэнса, опубликованный в 1983 году, и два графа Эллингема-Хортона (54 и 78 вершин). ^[4]^[5]

Первый график Эллингема-Хортона был опубликован Эллингемом в 1981 году и имел порядок 78. ^[6] На тот момент это был самый маленький из известных контрпримеров гипотезе Тутте. Второй был опубликован Эллингемом и Хортоном в 1983 году и имел номер 54. ^[7] В 1989 году был открыт граф Жоржа, самый маленький из известных в настоящее время негамильтоновых трехсвязных кубических двудольных графов, содержащий 50 вершин. ^[8]

Будучи негамильтоновым кубическим графом со многими длинными циклами, граф Хортона является хорошим ориентиром для программ, которые ищут гамильтоновы циклы. ^[9]

Граф Хортона имеет хроматическое число 2, хроматический индекс 3, радиус 10, диаметр 10, обхват 6, толщину книги 3. ^[10] и очередь номер 2. ^[10] Это также 3- реберно-связный граф .

Алгебраические свойства

Группа автоморфизмов графа Хортона имеет порядок 96 и изоморфна Z /2 Z × Z /2 Z × S ₄ , прямому произведению четырехгруппы Клейна и симметрической группы S ₄ .

Характеристический полином графа Хортона: $(x-3)(x-1)^{14}x^{4}(x+1)^{14}(x+3)(x^{2}-5)^{3}(x^{2}-3)^{11}(x^{2}-x-3)(x^{2}+x-3)$ $(x^{10}-23x^{8}+188x^{6}-644x^{4}+803x^{2}-101)^{2}$ $(x^{10}-20x^{8}+143x^{6}-437x^{4}+500x^{2}-59)$ .

Галерея

Хроматическое число графа Хортона равно 2.
графа Хроматический индекс Хортона равен 3.
, 54-граф Эллингема-Хортона меньший контрпример к гипотезе Тутте.

Ссылки

^ «График Хортона» . Архивировано из оригинала 4 марта 2016 г. Проверено 19 февраля 2022 г. {{cite web}}: CS1 maint: bot: исходный статус URL неизвестен ( ссылка )
^ Тутте, В.Т. «О двух факторах бикубических графов». Дискретная математика. 1, 203–208, 1971/72.
^ Бонди, Дж. А. и Мерти, Теория графов USR с приложениями. Нью-Йорк: Северная Голландия, с. 240, 1976.
^ Хортон, JD «О двух факторах двудольных регулярных графов». Дискретная математика. 41, 35–41, 1982.
^ Оуэнс, П.Дж. «Двудольные кубические графы и показатель краткости». Дискретная математика. 44, 327–330, 1983.
^ Эллингем, Миннесота «Негамильтоновы 3-связные кубические дробные графы». Отчет об исследовании № 28, факультет математики, Univ. Мельбурн, Мельбурн, 1981 год.
^ Эллингем, Миннесота и Хортон, Дж. Д. «Негамильтоновы 3-связные кубические двудольные графы». Дж. Комбин. Т.е. Сер. Б 34, 350-353, 1983.
^ Жорж, JP (1989), «Негамильтоновы бикубические графы», Журнал комбинаторной теории, серия B , 46 (1): 121–124, doi : 10.1016/0095-8956(89)90012-9 .
^ В. Ежов, Н. Пугачева, С. Россомахин, П. Зограф «Эффективный алгоритм перечисления реберных раскрасок и гамильтоновых циклов в кубических графах» arXiv:math/0610779v1 .
^ Перейти обратно: ^а ^б Джессика Вольц, «Разработка линейных макетов с помощью SAT» . Магистерская диссертация, Тюбингенский университет, 2018 г.

[1] «График Хортона» . Архивировано из оригинала 4 марта 2016 г. Проверено 19 февраля 2022 г. {{cite web}}: CS1 maint: bot: исходный статус URL неизвестен ( ссылка )

[2] Тутте, В.Т. «О двух факторах бикубических графов». Дискретная математика. 1, 203–208, 1971/72.

[3] Бонди, Дж. А. и Мерти, Теория графов USR с приложениями. Нью-Йорк: Северная Голландия, с. 240, 1976.

[4] Хортон, JD «О двух факторах двудольных регулярных графов». Дискретная математика. 41, 35–41, 1982.

[5] Оуэнс, П.Дж. «Двудольные кубические графы и показатель краткости». Дискретная математика. 44, 327–330, 1983.

[6] Эллингем, Миннесота «Негамильтоновы 3-связные кубические дробные графы». Отчет об исследовании № 28, факультет математики, Univ. Мельбурн, Мельбурн, 1981 год.

[7] Эллингем, Миннесота и Хортон, Дж. Д. «Негамильтоновы 3-связные кубические двудольные графы». Дж. Комбин. Т.е. Сер. Б 34, 350-353, 1983.

[8] Жорж, JP (1989), «Негамильтоновы бикубические графы», Журнал комбинаторной теории, серия B , 46 (1): 121–124, doi : 10.1016/0095-8956(89)90012-9 .

[9] В. Ежов, Н. Пугачева, С. Россомахин, П. Зограф «Эффективный алгоритм перечисления реберных раскрасок и гамильтоновых циклов в кубических графах» arXiv:math/0610779v1 .

[:0-10] Перейти обратно: ^а ^б Джессика Вольц, «Разработка линейных макетов с помощью SAT» . Магистерская диссертация, Тюбингенский университет, 2018 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]