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

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

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

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

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

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

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

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

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

Галерея

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

Посилання

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

Примітки

1. Weisstein, Eric W. Balaban 11-Cage(англ.) на сайті Wolfram MathWorld.
2. Balaban, Alexandru T., Trivalent graphs of girth nine and eleven, and relationships among cages, Revue Roumaine de Mathématiques Pures et Appliquées 18 (1973), 1033—1043. MR0327574 (англ.)
3. Weisstein, Eric W. Cage Graph(англ.) на сайті Wolfram MathWorld.
4. Geoffrey Exoo & Robert Jajcay, Dynamic cage survey, Electr. J. Combin. 15 (2008) (англ.)
5. Maher Heal, (2016)(англ.)
6. P. Eades, J. Marks, P. Mutzel, S. North, Graph-Drawing Contest Report, Mitsubishi Electric Research Laboratories, TR98-16, 1998(англ.)

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

• 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