Граф Харриса

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

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

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

Галерея

Примечания
  1. Weisstein, Eric W. Harries Graph (англ.) на сайте Wolfram MathWorld.
  2. Balaban, 1972, с. 1-5.
  3. Pisanski, Boben, Marušič, Orbanić, 2001.
  4. O'Keefe, Wong, 1980, с. 91-105.
  5. Bondy, Murty, 1976, с. 237.

Литература
  • 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.