11-клетка Балабана

11-клетка Балабана
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-клетки Балабана равен: $(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}(x^{5}+x^{4}-8x^{3}-6x^{2}+12x+4)^{8}$ .

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

Галерея

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

Примечания

↑ Weisstein, Eric W. Balaban 11-Cage (англ.) на сайте Wolfram MathWorld.
↑ Balaban, 1973, с. 1033—1043.
↑ Weisstein, Eric W. Cage Graph (англ.) на сайте Wolfram MathWorld.
↑ ¹ ² Exoo, Jajcay, 2008.
↑ Heal, 2016.
↑ 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.

Похожие исследовательские статьи

В теории графов графом МакГи, или (3-7)-клеткой, называется 3-регулярный граф с 24 вершинами и 36 рёбрами.

Граф Фрухта — определённый планарный минимальный кубический граф, не имеющий нетривиальных автоморфизмов. Описан Робертом Фрухтом в 1939 году.

Граф Дика — 3-регулярный граф с 32 вершинами и 48 рёбрами, назван в честь Вальтера фон Дика .

Снарк Секереша — снарк с 50 вершинами и 75 рёбрами, пятый известный снарк. Открыт Дьёрдьем Секерешем в 1973 году.

Граф Татта — пример кубического полиэдрального графа, не являющегося гамильтоновым. Таким образом, он служит контрпримером к гипотезе Тэйта, предполагавшей, что любой 3-регулярный многогранник имеет гамильтонов цикл.

В теории графов Граф Голднера — Харари — это простой неориентированный граф с 11 вершинами и 27 рёбрами. Файл назван в честь А. Голднера и Ф. Харари, которые в 1975 году доказали, что он является наименьшим негамильтоновым максимальным планарным графом. Тот же самый граф был уже приведён в качестве примера негамильтонова симплициального многогранника Грюнбаумом в 1967.

В теории графов граф Франклина — это 3-регулярный граф с 12 вершинами и 18 рёбрами.

В теории графов граф «бабочка» — это планарный неориентированный граф с 5 вершинами и 6 рёбрами. Граф может быть построен объединением двух копий циклов C₃ по одной общей вершине, а потому граф изоморфен графу дружеских отношений F₂.

В теории графов граф Харриса или (3-10)-клетка Харриса — это 3-регулярный неориентированный граф с 70 вершинами и 105 рёбрами.

В теории графов граф Харриса — Вонга — это 3-регулярный неориентированный граф с 70 вершинами и 105 рёбрами.

10-Клетка Балабана или балабанова (3,10)-клетка — это 3-регулярный граф с 70 вершинами и 105 рёбрами, названный именем химика румынского происхождения А.Т. Балабана. Опубликован в 1972. Это была первая обнаруженная (3,10)-клетка, но не единственная.

Алмаз — планарный неориентированный граф с 4 вершинами и 5 рёбрами. Граф представляет собой полный граф $\text{[math]}$ без одного ребра.

12-клетка Татта — 3-регулярный граф с 126 вершинами и 189 рёбрами, названный в честь Уильяма Татта.

Граф Фолкмана — это двудольный 4-регулярный граф с 20 вершинами и 40 рёбрами.

Граф Холта или граф Дойла является наименьшим полутранзитивным графом, то есть наименьшим примером вершинно-транзитивного и рёберно-транзитивного графа, который не является симметричным. Такие графы не часто встречаются. Граф назван именами Питера Дж. Дойла и Дерека Ф. Холта, обнаружившими граф независимо в 1976 и 1981 соответственно.

Граф Робертсона или (4,5)-клетка — это 4-регулярный неориентированный граф с 19 вершинами и 38 рёбрами, названный именем Нейла Робертсона.

Граф Робертсона — Вегнера — 5-регулярный неориентированный граф с 30 вершинами и 75 рёбрами, названный именами Нейла Робертсона и Дж. Вегнера.

Клетка Фостера — 5-регулярный неориентированный граф с 30 вершинами и 75 рёбрами. Граф является одной из четырёх (5,5)-клеток, другие три: граф Мерингера, граф Робертсона — Вегнера и граф Вонга.

Граф Мередита — 4-регулярный неориентированный граф с 70 вершинами и 140 рёбрами, обнаруженный Гаем Мередитом в 1973 году.

Бидиакис-куб — это 3-регулярный граф с 12 вершинами и 18 рёбрами.

Эта страница основана на статье Википедии.
Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия.
Изображения, видео и звуки доступны по их собственным лицензиям.