В математической области теории графов , в графе Харриеса или Харрис (3-10) -cage представляет собой 3- регулярный неориентированный граф с 70 вершинами и 105 ребер. [1]
Граф Харриса | |
---|---|
Вершины | 70 |
Края | 105 |
Радиус | 6 |
Диаметр | 6 |
Обхват | 10 |
Автоморфизмы | 120 ( S 5 ) |
Хроматическое число | 2 |
Хроматический индекс | 3 |
Толщина книги | 3 |
Номер очереди | 2 |
Характеристики | Гамильтониан без треугольников в кубической клетке |
Таблица графиков и параметров |
Граф Харриса имеет хроматическое число 2, хроматический индекс 3, радиус 6, диаметр 6, обхват 10 и является гамильтоновым . Это также непланарный кубический граф с 3- вершинно-связными и 3- реберно-связными . Он имеет книжную толщину 3 и номер очереди 2. [2]
Характеристический полином графа Харриес является
История
В 1972 году А.Т. Балабан опубликовал (3-10) -клеточный граф , кубический граф, имеющий как можно меньше вершин для обхвата 10. [3] Это была первая обнаруженная (3-10) -клетка, но она не была уникальной. . [4]
Полный список (3-10) -клеток и доказательство минимальности были даны О'Кифом и Вонгом в 1980 году. [5] Существует три различных (3-10) -клеточных графа - 10- клеточный Балабан и Граф Харриса и граф Харриса – Вонга . [6] Кроме того, граф Харриса – Вонга и граф Харриса являются коспектральными графами .
Галерея
Хроматическое число графа Харриса равно 2.
Хроматический индекс графа Харриса равен 3.
Альтернативный рисунок графа Харриса.
Рекомендации
- ^ Weisstein, Эрик В. "График Харриса" . MathWorld .
- ^ Джессика Wolz, Инженерная Линейные Макеты с SAT . Магистерская работа, Тюбингенский университет, 2018 г.
- ^ А. Т. Балабан, трехвалентный граф обхвата десять, J. Combin. Теория Сер. В 12, 1-5. 1972 г.
- ^ Писанский, Т .; Boben, M .; Марушич, Д .; и Орбанич, А. "Обобщенные конфигурации Балабана". Препринт. 2001. [1] .
- ^ М. О'Киф и П.К. Вонг, Наименьший граф обхвата 10 и валентности 3, J. Combin. Теория Сер. В 29 (1980) 91-105.
- ^ Бонди, Дж. А. и Мерти, Теория графов USR с приложениями. Нью-Йорк: Северная Голландия, стр. 237, 1976.