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-связным и рёберно 3-связным графом.

Алгебраические свойства

Характеристический многочлен 11-клетки Балабана равен: .

Группа автоморфизмов графа имеет порядок 64[4].

Галерея

Примечания

  1. Weisstein, Eric W. Balaban 11-Cage (англ.) на сайте Wolfram MathWorld.
  2. Balaban, 1973, с. 1033—1043.
  3. Weisstein, Eric W. Cage Graph (англ.) на сайте Wolfram MathWorld.
  4. Exoo, Jajcay, 2008.
  5. Heal, 2016.
  6. 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.