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-клітки Балабана дорівнює:

( x − 3 ) x 12 ( x 2 − 6 ) 5 ( x 2 − 2 ) 12 ( x 3 − x 2 − 4 x + 2 ) 2 ⋅ {\displaystyle (x-3)x^{12}(x^{2}-6)^{5}(x^{2}-2)^{12}(x^{3}-x^{2}-4x+2)^{2}\cdot } ⋅ ( x 3 + x 2 − 6 x − 2 ) ( x 4 − x 3 − 6 x 2 + 4 x + 4 ) 4 ( x 5 + x 4 − 8 x 3 − 6 x 2 + 12 x + 4 ) 8 {\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]

Галерея

Посилання

Примітки

  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