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

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

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

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-клітка Балабана (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