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

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

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

11-клітка Балабана є єдиною (3-11)-кліткою. Граф відкрив Олександру Балабан в 1973 р.[2] Унікальність була доведена Бренданом Маккеєм та Вендою Мирвольд у 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.