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

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

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

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

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

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

Характеристичний поліном 11-клітки Балабана дорівнює:

   .

Група автоморфізму 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