11-клетка Балабана

11-клетка Балабана
11-клетка Балабана
Назван в честь	Александру Т. Балабана
Вершин	112
Рёбер	168
Радиус	6
Диаметр	8
Обхват	11
Автоморфизмы	64
Хроматическое число	3
Хроматический индекс	3
Свойства	Кубический Клетка Гамильтонов
Медиафайлы на Викискладе

11-клетка Балабана или (3-11)-клетка Балабана — это 3-регулярный граф с 112 вершинами и 168 рёбрами, названные именем румынского химика Александру Т. Балабана[1].

11-клетка Балабана является единственной (3-11)-клеткой. Граф открыл Балабан в 1973 году[2]. Единственность её доказали Брендан Маккей и Венди Мирволд в 2003 году[3].

Свойства

11-клетка Балабана является гамильтоновым графом и может быть построена путём удаления из 12-клетки Татта малого поддерева и получающихся в результате вершин степени два[4].

Граф имеет число независимости 52[5], хроматическое число 3, хроматический индекс 3, радиус 6, диаметр 8 и обхват 11. Он также является вершинно 3-связным и рёберно 3-связным графом.

Алгебраические свойства

Характеристический многочлен 11-клетки Балабана равен: ${\displaystyle (x-3)x^{12}(x^{2}-6)^{5}(x^{2}-2)^{12}(x^{3}-x^{2}-4x+2)^{2}\cdot }$ ${\displaystyle \cdot (x^{3}+x^{2}-6x-2)(x^{4}-x^{3}-6x^{2}+4x+4)^{4}(x^{5}+x^{4}-8x^{3}-6x^{2}+12x+4)^{8}}$.

Группа автоморфизмов графа имеет порядок 64[4].

Галерея

• 
  Хроматическое число 11-клетки Балабана равен 3.
• 
  Хроматический индекс 11-клетки Балабана равен 3.
• 
  Альтернативный рисунок 11-клетки Балабана[6]

Примечания

1. Weisstein, Eric W. Balaban 11-Cage (англ.) на сайте Wolfram MathWorld.
2. Balaban, 1973, с. 1033—1043.
3. Weisstein, Eric W. Cage Graph (англ.) на сайте Wolfram MathWorld.
4. Exoo, Jajcay, 2008.
5. Heal, 2016.
6. Eades, Marks, Mutzel, North, 1998.

Литература

• Alexandru T. Balaban. Trivalent graphs of girth nine and eleven, and relationships among cages // Revue Roumaine de Mathématiques Pures et Appliquées. — 1973. — Т. 18.
• Geoffrey Exoo, Robert Jajcay. Dynamic cage survey // Electr. J. Combin.. — 2008. — Вып. 15.
• Maher Heal. A Quadratic Programming Formulation to Find the Maximum Independent Set of Any Graph // The 2016 International Conference on Computational Science and Computational Intelligence. — Las Vegas: IEEE Computer Society, 2016.
• Eades P., Marks J., Mutzel P., North S. Graph-Drawing Contest Report // TR98-16. — Mitsubishi Electric Research Laboratories, 1998.