График Харриса – Вонга - Harries–Wong graph

График Харриса – Вонга
Харрис-вонг graph.svg
Граф Харриса – Вонга
Вершины70
Края105
Радиус6
Диаметр6
Обхват10
Автоморфизмы24 (S4 )
Хроматическое число2
Хроматический индекс3
Толщина книги3
Номер очереди2
ХарактеристикиКубический
Клетка
Без треугольников
Гамильтониан
Таблица графиков и параметров

в математический поле теория графов, то График Харриса – Вонга это 3-обычный неориентированный граф с 70 вершинами и 105 ребрами.[1]

Граф Харриса – Вонга имеет хроматическое число 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] Более того, граф Харриса – Вонга и граф Харриза являются кососпектральные графики.

Галерея

Рекомендации

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