Балабан 11-клеточный

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

В математической области теории графов или 11-клетка Балабана ( 3,11)-клетка Балабана представляет собой 3- правильный граф со 112 вершинами и 168 ребрами, названный в честь Александру Т. Балабана .

Клетка Balaban 11 – это уникальная (3,11) -клетка . Он был открыт Балабаном в 1973 году. Уникальность доказали Брендан Маккей и Венди Мирволд в 2003 году.

11-клетка Балабана является гамильтоновым графом и может быть построена путем вырезания 12-клетки Тутте путем удаления небольшого поддерева и подавления полученных вершин второй степени.

Он имеет номер независимости 52, хроматическое число 3, хроматический индекс 3, радиус 6, диаметр 8 и обхват 11. Это также 3 -связный граф и 3 -связный граф .

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

$(x-3)x^{12}(x^{2}-6)^{5}(x^{2}-2)^{12}(x^{3}-x^{2}-4x+2)^{2}\cdot$

$\cdot (x^{3}+x^{2}-6x-2)(x^{4}-x^{3}-6x^{2}+4x+4)^{4}\cdot$

$\cdot (x^{5}+x^{4}-8x^{3}-6x^{2}+12x+4)^{8}$.

Группа автоморфизмов 11-клетки Балабана имеет порядок 64.

Галерея

• 
  Хроматическое число клетки Балабана 11 равно 3.
• 
  Хроматический индекс Балабана 11-клетки равен 3.
• 
  Альтернативный рисунок Балабана 11-клетки.

Ссылки

• Хил, Махер (2016), «Формулировка квадратичного программирования для поиска максимального независимого набора любого графа», Международная конференция по вычислительной науке и вычислительному интеллекту 2016 года , Лас-Вегас: Компьютерное общество IEEE