Interested Article - 11-клетка Балабана
- 2021-07-12
- 1
11-клетка Балабана или (3-11)-клетка Балабана — это 3- регулярный граф с 112 вершинами и 168 рёбрами, названные именем румынского химика Александру Т. Балабана .
11-клетка Балабана является единственной (3-11)-клеткой . Граф открыл Балабан в 1973 году . Единственность её доказали Брендан Маккей и Венди Мирволд в 2003 году .
Свойства
11-клетка Балабана является гамильтоновым графом и может быть построена путём удаления из 12-клетки Татта малого поддерева и получающихся в результате вершин степени два .
Граф имеет число независимости 52 , хроматическое число 3, хроматический индекс 3, радиус 6, диаметр 8 и обхват 11. Он также является вершинно 3-связным и рёберно 3-связным графом.
Алгебраические свойства
Характеристический многочлен 11-клетки Балабана равен: .
Группа автоморфизмов графа имеет порядок 64 .
Галерея
-
Хроматическое число 11-клетки Балабана равен 3.
-
Хроматический индекс 11-клетки Балабана равен 3.
-
Альтернативный рисунок 11-клетки Балабана
Примечания
Литература
- 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.
- 2021-07-12
- 1