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

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

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

Балабан 11-клетка - уникальная (3-11) клетка . Он был открыт Балабаном в 1973 году. ^[2] Уникальность была доказана Бренданом Маккей и Венди Мирволд в 2003 году. ^[3]

11-клетка Балабана является гамильтоновым графом и может быть построена путем вырезания из 12-клетки Тутте путем удаления небольшого поддерева и подавления результирующих вершин степени два. ^[4]

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

Алгебраические свойства [ править ]

Характеристический полином от Balaban 11-клетки: . ${\ displaystyle (x-3) x ^ {12} (x ^ {2} -6) ^ {5} (x ^ {2} -2) ^ {12} (x ^ {3} -x ^ {2 } -4x + 2) ^ {2} \ cdot}$ ${\ displaystyle \ cdot (x ^ {3} + x ^ {2} -6x-2) (x ^ {4} -x ^ {3} -6x ^ {2} + 4x + 4) ^ {4} ( x ^ {5} + x ^ {4} -8x ^ {3} -6x ^ {2} + 12x + 4) ^ {8}}$

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

Галерея [ править ]

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

Ссылки [ править ]

Перейти ↑ Weisstein, Eric W. Balaban 11-Cage . MathWorld .
↑ Балабан, Александру Т. , Трехвалентные графики девятого и одиннадцатого обхвата и отношения между клетками , Revue Roumaine de Mathématiques Pures et Appliquées 18 (1973), 1033-1043. Руководство по ремонту 0327574
^ Weisstein, Эрик В. "График клетки" . MathWorld .
^ a b Джеффри Эксу и Роберт Джейчай, Динамическое обследование клетки, Электр. J. Combin. 15 (2008)
^ Махер Хил (2016)
^ П. Идс , Дж. Маркс, П. Муцель , С. Норт. «Отчет о конкурсе графического рисунка», TR98-16, декабрь 1998 г., Mitsubishi Electric Research Laboratories.

Ссылки [ править ]

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

[1] Перейти ↑ Weisstein, Eric W. Balaban 11-Cage . MathWorld .

[2] Балабан, Александру Т. , Трехвалентные графики девятого и одиннадцатого обхвата и отношения между клетками , Revue Roumaine de Mathématiques Pures et Appliquées 18 (1973), 1033-1043. Руководство по ремонту 0327574

[3] Weisstein, Эрик В. "График клетки" . MathWorld .

[SURV-4] Джеффри Эксу и Роберт Джейчай, Динамическое обследование клетки, Электр. J. Combin. 15 (2008)

[5] Махер Хил (2016)

[6] П. Идс , Дж. Маркс, П. Муцель , С. Норт. «Отчет о конкурсе графического рисунка», TR98-16, декабрь 1998 г., Mitsubishi Electric Research Laboratories.

[1]