Граф Харриса

Шаблон:Граф

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

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

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

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

История

В 1972 А. Т. Балабан (A.T. Balaban) опубликовал (3-10)-клетку, кубический граф, который имеет минимальное количество вершин для обхвата 10Шаблон:Sfn. Это была первая открытая (3-10)-клетка, но она не уникальнаШаблон:Sfn.

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