Балабан 10-клеточный

Кубический граф с 70 узлами и 105 ребрами

В математической области теории графов 10-клетка Балабана или ( 3,10) -клетка Балабана представляет собой 3- регулярный граф с 70 вершинами и 105 ребрами, названный в честь Александру Т. Балабана . ^[1] Опубликовано в 1972 году, ^[2] Это была первая обнаруженная 10- клетка , но она не является уникальной. ^[3]

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

Десятиклетка Балабана имеет хроматическое число 2, хроматический индекс 3, диаметр 6, обхват 10 и является гамильтоновой . Это также граф с 3 вершинами и 3 ребрами . Толщина книги равна 3, а число очередей равно 2. ^[6]

Характеристический полином 10-клетки Балабана равен

${\displaystyle (x-3)(x-2)(x-1)^{8}x^{2}(x+1)^{8}(x+2)(x+3)\cdot }$

${\displaystyle \cdot (x^{2}-6)^{2}(x^{2}-5)^{4}(x^{2}-2)^{2}(x^{4}-6x^{2}+3)^{8}.}$

Галерея

• 
  Хроматическое число 10-клеточного аппарата Балабана равно 2.
• 
  Хроматический индекс 10-клеточного Balaban равен 3.
• 
  Еще один рисунок 10-клеточного Балабана.

Смотрите также

Молекулярный граф
Балабан 11-клеточный

Ссылки

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