График Мередита - Meredith graph
| График Мередита | |
|---|---|
 График Мередита | |
| Названный в честь | Г. Х. Мередит |
| Вершины | 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]
В характеристический многочлен графа Мередита .
Галерея
В хроматическое число графа Мередита равно 3.
В хроматический индекс графа Мередита равно 5.
Рекомендации
- ^ Вайсштейн, Эрик В. «График Мередита». MathWorld.
- ^ Бонди, Дж. А. и Мурти, США, "Теория графов". Спрингер, стр. 470, 2007.
- ^ Джессика Вольц, Инженерные линейные схемы с SAT. Магистерская работа, Тюбингенский университет, 2018 г.
- ^ Мередит, Г. Х. Дж. «Регулярные 4-валентные 4-связные негамильтоновы не-4-реберные графы». J. Combin. Чт. В 14, 55-60, 1973.
- ^ Бонди, Дж. А. и Мурти, США, "Теория графов с приложениями". Нью-Йорк: Северная Голландия, стр. 239, 1976.
- ^ Тутте, У.Т., под ред., Последние достижения в комбинаторике. Academic Press, Нью-Йорк, 1969.