График Мередит

График Мередит
График Мередит
	Граф Мередит
Назван в честь	Г.Х. Мередит
Вершины	70
Края	140
Радиус	7
Диаметр	8
Обхват	4
Автоморфизмы	38698352640
Хроматическое число	3
Хроматический индекс	5
Толщина книги	3
Номер очереди	2
Характеристики	Эйлеров
	Таблица графиков и параметров

В математической области теории графов граф Мередита представляет собой 4- регулярный неориентированный граф с 70 вершинами и 140 ребрами, открытый Гаем Х. Дж. Мередитом в 1973 году. ^[1]

Граф Мередита 4 -связен по вершинам и 4 -связен по ребрам , имеет хроматическое число 3, хроматический индекс 5, радиус 7, диаметр 8, обхват 4 и не является гамильтоновым . ^[2] Имеет толщину книги 3 и номер очереди 2. ^[3]

Опубликованный в 1973 году, он представляет собой контрпример к гипотезе Криспина Нэша-Уильямса о том, что каждый 4-регулярный 4-связный граф является гамильтоновым. ^[4]^[5] Однако У.Т.Татт показал, что все 4-связные плоские графы гамильтоновы. ^[6]

Характеристический полином графа Мередита равен $(x-4)(x-1)^{10}x^{21}(x+1)^{11}(x+3)(x^{2}-13)(x^{6}-26x^{4}+3x^{3}+169x^{2}-39x-45)^{4}$ .

Галерея

Хроматическое число графа Мередита равно 3.
Хроматический индекс графа Мередита равен 5.

Ссылки

^ Вайсштейн, Эрик В. «График Мередит» . Математический мир .
^ Бонди, Дж. А. и Мурти, USR «Теория графов». Спрингер, с. 470, 2007.
^ Джессика Вольц, Разработка линейных макетов с помощью SAT . Магистерская диссертация, Тюбингенский университет, 2018 г.
^ Мередит, GHJ (1973). «Регулярные $n$ -валентные $n$ -связные негамильтоновы не $n$ -раскрашиваемые графы» . Журнал комбинаторной теории, серия B. 14 :55–60. дои : 10.1016/s0095-8956(73)80006-1 . МР 0311503 .
^ Бонди, Дж. А. и Мурти, USR «Теория графов с приложениями». Нью-Йорк: Северная Голландия, с. 239, 1976.
^ Тутте, WT, изд., Недавний прогресс в комбинаторике. Академик Пресс, Нью-Йорк, 1969.

[1] Вайсштейн, Эрик В. «График Мередит» . Математический мир .

[2] Бонди, Дж. А. и Мурти, USR «Теория графов». Спрингер, с. 470, 2007.

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

[4] Мередит, GHJ (1973). «Регулярные $n$ -валентные $n$ -связные негамильтоновы не $n$ -раскрашиваемые графы» . Журнал комбинаторной теории, серия B. 14 :55–60. дои : 10.1016/s0095-8956(73)80006-1 . МР 0311503 .

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

[6] Тутте, WT, изд., Недавний прогресс в комбинаторике. Академик Пресс, Нью-Йорк, 1969.

[1]

[2]

[3]

[4]

[5]

[6]