Граф Харриса — Вонга

В теории графов граф Харриса — Вонга — это 3-регулярный неориентированный граф с 70 вершинами и 105 рёбрами.

Граф Харриса – Вонга
Вершин	70
Рёбер	105
Радиус	6
Диаметр	6
Обхват	10
Автоморфизмы	24 (S4)
Хроматическое число	2
Хроматический индекс	3
Свойства	кубический клетка без треугольников гамильтонов

Хроматическое число графа равно 2, хроматический индекс равен 3, диаметр графа и радиус равны 6, а обхват равен 10.

Граф является гамильтоновым, вершинно 3-связным, рёберно 3-связным, планарным кубическим графом.

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

$(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.$$(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 году А. Т. Балабан (A. T. Balaban) опубликовал (3-10)-клетку, кубический граф, который имеет минимальное количество вершин для обхвата 10. Это была первая открытая (3-10)-клетка, но она не уникальна.

Полный список (3-10)-клеток и доказательство минимальности дали О’Киф (O’Keefe) и Вонг (Wong) в 1980. Существует только три различных (3-10)-клетки — 10-клетка Балабана, граф Харриса и граф Харриса — Вонга. Более того, граф Харриса — Вонга и граф Харриса являются коспектральными графами.

ГалереяПравить

•  

  Хроматическое число графа Харриса — Вонга равно 2.

•  

  Хроматический индекс графа Харриса — Вонга равен 3.

•  

  Альтернативный рисунок графа Харриса — Вонга.

•  

  8 орбит графа Харриса — Вонга.

ЛитератураПравить

• A. T. Balaban. A trivalent graph of girth ten // J. Combin. Theory Ser. B. — 1972. — Вып. 12. — С. 1-5.
• T. Pisanski, M. Boben, D. Marušič, A. Orbanić. The Generalized Balaban Configurations // Preprint. — 2001.
• M. O'Keefe, P.K. Wong. A smallest graph of girth 10 and valency 3 // J. Combin. Theory Ser. B. — 1980. — Вып. 29.
• J. A. Bondy, U. S. R. Murty. Graph Theory with Applications. — New York: North Holland, 1976. — С. 237.