Граф Харриса


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

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

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

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