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

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

Назван в честь	А.Т. Балабана^[англ.]
Вершин	70
Рёбер	105
Радиус	6
Диаметр	6
Обхват	10
Автоморфизмы	80
Хроматическое число	2
Хроматический индекс	3
Свойства	Кубический Клетка Гамильтонов
Медиафайлы на Викискладе

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

(3-10)-клетки

Полный список (3-10)-клеток дали и доказали минимальность О'Кииф и Вонг^[4]. Существует 3 различные (3-10)-клетки, две другие — граф Харриса и граф Харриса – Вонга^[5]. Однако граф Харриса – Вонга и граф Харриса — являются коспектральными.

Свойства

10-Клетка Балабана имеет хроматическое число 2, хроматический индекс 3, диаметр 6, обхват 10 и граф является гамильтоновым. Граф является также вершинно 3-связным и рёберно 3-связным.

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

(x-3)(x-2)(x-1)^{8}x^{2}(x+1)^{8}(x+2)(x+3)(x^{2}-6)^{2}(x^{2}-5)^{4}(x^{2}-2)^{2}(x^{4}-6x^{2}+3)^{8}.

Галерея

Хроматическое число 10-клетки Балабана равно 2.
Хроматический индекс 10-клетки Балабана равен 3.
Альтернативное представление 10-клетки Балабана.

См. также

Молекулярный граф

Примечания

↑ Weisstein, Eric W. Balaban 10-Cage (англ.) на сайте Wolfram MathWorld.
↑ Balaban, 1972, с. 1-5.
↑ Pisanski, Boben, Marušič, Orbanić, 2001.
↑ O'Keefe, Wong, 1980, с. 91–105.
↑ Bondy, Murty, 1976, с. 237.

Литература

A. T. Balaban. A trivalent graph of girth ten // J. Combin. Theory. — 1972. — Вып. 12.
M. O'Keefe, P.K. Wong. A smallest graph of girth 10 and valency 3 // J. Combin. Theory. — 1980. — Вып. 29.
T. Pisanski, M. Boben, D. Marušič, A. Orbanić. The Generalized Balaban Configurations. — 2001. — Т. 39. — ISSN 1318-4865.
J. A. Bondy, U. S. R. Murty. Graph Theory with Applications. — New York: North Holland, 1976. — ISBN 0-444-19451-7.

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

Обхват графа — длина наименьшего цикла, содержащегося в данном графе. Если граф не содержит циклов, его обхват по определению равен бесконечности. Например, 4-цикл (квадрат) имеет обхват 4. Квадратная решётка имеет также обхват 4, а треугольная сетка имеет обхват 3. Граф с обхватом четыре и более не имеет треугольников.

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

Граф Хивуда — ненаправленный граф с 14 вершинами и 21 ребром, названный в честь Перси Джона Хивуда.

Граф Грея — двудольный неориентированный граф с 54 вершинами и 81 рёбрами. Граф является кубическим — любая вершина принадлежит ровно трём рёбрам. Граф был открыт Греем в 1932 году, затем открыт независимо Баувером (Bouwer) в 1968 году в ответ на вопрос, поставленный Фолкманом в 1967 году. Граф Грея примечателен как исторически первый пример кубического графа, имеющего алгебраическое свойство рёберной, но не вершинной транзитивности.

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

Граф Вагнера — 3-регулярный граф с 8 вершинами и 12 рёбрами, является 8-вершинной лестницей Мёбиуса.

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

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

Граф Хортона — 3-регулярный граф с 96 вершинами и 144 рёбрами, открытый Джозефом Хортоном. Бонди и Мурти опубликовали в 1976 этот граф в качестве контрпримера гипотезе Татта, что любой кубический 3-связный двудольный граф является гамильтоновым.

Степень k неориентированного графа G — это другой граф, имеющий тот же самый набор вершин, и две вершины этого графа смежны, если расстояние между этими вершинами в исходном графе G не превышает k. Для указания степени графа используется терминология, аналогичная степеням чисел — G² называется квадратом графа G, G³ называется кубом.

Графы Эллингема — Хортона — два 3-регулярных графа с 54 и 78 вершинами — 54-граф Эллингема — Хортона и 78-граф Эллингема — Хортона. Графы названы именами Джозефа Хортона и Марка Эллингема, которые их открыли. Эти два графа дают контрпримеры гипотезе Уильяма Татта о том, что каждый кубический 3-связный двудольный граф является гамильтоновым.

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

Граф Любляны — неориентированный двудольный граф с 112 вершинами и 168 рёбрами.

110-вершинный граф Иванова — Иофиновой — полусимметричный кубический граф с 110 вершинами и 165 рёбрами.

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

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

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

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

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

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

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