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

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

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

Свойства

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

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

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

Характеристический многочлен 11-клетки Балабана равен: $(x-3)x^{12}(x^2-6{)}^5(x^2-2{)}^{12}(x^3-x^2-4x+2{)}^2\cdot$ $\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Шаблон:Sfn.

Галерея

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

Литература

• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга