11-клетка Балабана
11-клетка Балабана или (3-11)-клетка Балабана — это 3-регулярный граф с 112 вершинами и 168 рёбрами, названные именем румынского химика Александру Т. Балабана[1].
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-связным и рёберно 3-связным графом.
Алгебраические свойства
Характеристический многочлен 11-клетки Балабана равен: .
Группа автоморфизмов графа имеет порядок 64[4].
Галерея
- Хроматическое число 11-клетки Балабана равен 3.
- Хроматический индекс 11-клетки Балабана равен 3.
- Альтернативный рисунок 11-клетки Балабана[6]
Примечания
- Weisstein, Eric W. Balaban 11-Cage (англ.) на сайте Wolfram MathWorld.
- Balaban, 1973, с. 1033—1043.
- Weisstein, Eric W. Cage Graph (англ.) на сайте Wolfram MathWorld.
- Exoo, Jajcay, 2008.
- Heal, 2016.
- Eades, Marks, Mutzel, North, 1998.
Литература
- Alexandru T. Balaban. Trivalent graphs of girth nine and eleven, and relationships among cages // Revue Roumaine de Mathématiques Pures et Appliquées. — 1973. — Т. 18.
- Geoffrey Exoo, Robert Jajcay. Dynamic cage survey // Electr. J. Combin.. — 2008. — Вып. 15.
- Maher Heal. 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, 2016.
- Eades P., Marks J., Mutzel P., North S. Graph-Drawing Contest Report // TR98-16. — Mitsubishi Electric Research Laboratories, 1998.