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

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

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

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

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

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

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

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

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

Галерея

Рекомендации

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

Рекомендации

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