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

У математичної області теорії графів 11-клітка Балабана або (3-11) клітки Балабана — це 3-регулярний граф зі 112-ма вершинами й 168-ма ребрами, названі ім'ям румунського хіміка Александру Балабана.

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

11-клітка Балабана є єдиною (3-11)-кліткою. Граф відкрив Александру Балабан в 1973 р. Унікальність довели Брендан Маккей і Венді Мирвольд у 2003 році.

11-клітка Балабана є гамільтоновим графом і може бути побудована шляхом видалення з 12-клітки Татта малого піддерева та отриманих вершин другого ступеня.

Граф має число незалежності — 52, хроматичне число — 3, хроматичний індекс — 3, радіус — 6, діаметр — 8 і обхват — 11. Він також є 3- k-вершинно-зв'язним графом і 3- k-реберно-зв'язним графом.

Алгебраїчні властивості

Характеристичний поліном 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}$.

Група автоморфізму 11-клітки Балабана має порядок 64.

Галерея

• 
  Хроматичне число 11-клітки Балабана дорівнює 3.
• 
  Хроматичний індекс 11-клітки Балабана дорівнює 3.
• 
  Альтернативний малюнок 11-клітки Балабана.

Посилання

• Теорія графів
• Клітка (теорія графів)
• 10-клітка Балабана
• 11-клітка Балабана [Архівовано 19 січня 2019 у Wayback Machine.] (MathWorld) (англ.)

Список літератури

• Heal, Maher (2016), 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