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-клітки Балабана дорівнює:
.
Група автоморфізму 11-клітки Балабана має порядок 64.[4]
Галерея
- Хроматичне число 11-клітки Балабана дорівнює 3.
- Хроматичний індекс 11-клітки Балабана дорівнює 3.
- Альтернативний малюнок 11-клітки Балабана[6].
Посилання
- Теорія графів
- Клітка (теорія графів)
- 10-клітка Балабана[en]
- 11-клітка Балабана [Архівовано 19 січня 2019 у Wayback Machine.] (MathWorld) (англ.)
Примітки
- ↑ Weisstein, Eric W. Balaban 11-Cage(англ.) на сайті Wolfram MathWorld.
- ↑ 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 (англ.)
- ↑ Weisstein, Eric W. Cage Graph(англ.) на сайті Wolfram MathWorld.
- ↑ а б Geoffrey Exoo & Robert Jajcay, Dynamic cage survey, Electr. J. Combin. 15 (2008) (англ.)
- ↑ Maher Heal, (2016)(англ.)
- ↑ 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