График Харриса

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

В математической области теории графов граф Харриса или (3-10)-клетка Харриса представляет собой 3- регулярный неориентированный граф с 70 вершинами и 105 ребрами. ^[1]

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

Характеристический полином графа Харриса равен

(x-3)(x-1)^{4}(x+1)^{4}(x+3)(x^{2}-6)(x^{2}-2)(x^{4}-6x^{2}+2)^{5}(x^{4}-6x^{2}+3)^{4}(x^{4}-6x^{2}+6)^{5}.\,

История

В 1972 году А. Т. Балабан опубликовал граф (3-10)-клеток — кубический граф, имеющий как можно меньше вершин для обхвата 10. ^[3] Это была первая обнаруженная клетка (3-10), но она не была уникальной. ^[4]

Полный список (3-10)-клеток и доказательство минимальности были даны О'Кифом и Вонгом в 1980 году. ^[5] Существуют три различных графа (3-10) клеток — 10-клеточный граф Балабана , граф Харриса и граф Харриса-Вонга . ^[6] Более того, граф Харриса–Вонга и граф Харриса являются коспектральными графами .

Галерея

Хроматическое число графа Харриса равно 2.
Хроматический индекс графа Харриса равен 3.
Альтернативный рисунок графика Харриса.
Альтернативный рисунок, подчеркивающий 4 орбиты графа.

Ссылки

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

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

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

[3] А. Т. Балабан, Трехвалентный график обхвата десять, Дж. Комбин. Теория Сер. Б 12, 1-5. 1972.

[4] Пизански, Т.; Бобен, М.; Марушич, Д.; и Орбанич А. «Обобщенные конфигурации Балабана». Перепечатка. 2001. [1] .

[5] М. О'Киф и П.К. Вонг, Наименьший график обхвата 10 и валентности 3, Дж. Комбин. Теория Сер. Б 29 (1980) 91-105.

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

[1]

[2]

[3]

[4]

[5]

[6]