Граф МакГи

Перейти к навигации Перейти к поиску

Граф МакГи

Назван в честь	W. F. McGee
Вершин	24
Рёбер	36
Радиус	4
Диаметр	4
Обхват	7
Автоморфизмы	32
Хроматическое число	3
Хроматический индекс	3
Свойства	кубический клетка гамильтонов
Медиафайлы на Викискладе

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

Граф МакГи — это единственная (3,7)-клетка (наименьший кубический с обхватом 7). Он является наименьшей кубической клеткой, не являющейся графом Мура.

Впервые открытый Хорстом Саксом^[англ.], но не опубликованный^[2], граф назван в честь МакГи (W. F. McGee), который опубликовал результат в 1960 году^[3]. Позднее, в 1966 году, Уильям Томас Татт доказал, что это единственная (3,7)-клетка^[4]^[5]^[6].

Известны наименьшие кубические графы с числом скрещиваний 1—8 (последовательность A110507 в OEIS), наименьший граф с числом скрещиваний 8 — это граф МакГи. Существует 5 неизоморфных кубических графов порядка 24 с числом скрещиваний 8^[7], один из них — обобщённый граф Петерсена G(12,5), известный также как Граф Науру^[8].

Граф МакГи имеет радиус 4, диаметр 4, хроматическое число 3 и хроматический индекс 3. Он также 3-вершинно-связен и 3-рёберно-связен.

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

Характеристический многочлен графа МакГи равен $x^{3}(x-3)(x-2)^{3}(x+1)^{2}(x+2)(x^{2}+x-4)(x^{3}+x^{2}-4x-2)^{4}$ .

Автоморфизм группы графа МакГи имеет порядок 32 и не транзитивен относительно вершин — имеется две орбиты вершин длины 8 и 16. Граф МакГи — это наименьшая кубическая клетка, не являющаяся вершинно-транзитивной^[9].

Галерея

Число пересечений графа МакГи равно 8.
Хроматическое число графа МакГи равно 3.
Хроматический индекс графа МакГи ракен 3.
The Ациклический хроматический индекс графа МакГи равен 3.
Альтернативное изображение графа МакГи.

Примечания

↑ Weisstein, Eric W. McGee Graph (англ.) на сайте Wolfram MathWorld.
↑ Kárteszi, F. «Piani finit ciclici come risoluzioni di un certo problemo di minimo.» Boll. Un. Mat. Ital. 15, 522—528, 1960
↑ McGee, W. F. «A Minimal Cubic Graph of Girth Seven.» Canad. Math. Bull. 3, 149—152, 1960
↑ Tutte, W. T. Connectivity in Graphs. Toronto, Ontario: University of Toronto Press, 1966
↑ Wong, P. K. «Cages--A Survey.» J. Graph Th. 6, 1-22, 1982
↑ Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance Regular Graphs. New York: Springer-Verlag, p. 209, 1989
↑ Pegg, E. T. and Exoo, G. «Crossing Number Graphs.» Mathematica J. 11, 2009
↑ Weisstein, Eric W. Graph Crossing Number (англ.) на сайте Wolfram MathWorld.
↑ Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 237, 1976.

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

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

<span class="mw-page-title-main">Граф Грёча</span> граф без треугольников с 11 вершинами, 20 рёбрами, хроматическим числом 4 и числом скрещиваний 5

Граф Грёча — граф без треугольников с 11 вершинами, 20 рёбрами, хроматическим числом 4 и числом скрещиваний 5. Граф назван в честь немецкого математика Герберта Грёча и он демонстрирует необходимость предположения планарности в теореме Грёча, которая утверждает, что любой планарный граф без треугольников можно раскрасить в 3 цвета. Граф Грёча является членом бесконечной последовательности графов без треугольников, в которой каждый граф является мычельскианом предыдущего графа, начиная с нуль-графа. Эта последовательность графов была использована Мыцельским, чтобы показать, что существуют графы без треугольников с произвольно большим хроматическим числом. По этой причине иногда граф Грёча называют графом Мыцельского или Мыцельского-Грёча. В отличие от других, более поздних графов в последовательности, граф Грёча является наименьшим графом без треугольников с его хроматическим числом.

В теории графов колесом W_n называется граф с n вершинами (n ≥ 4), образованный соединением единственной вершины со всеми вершинами (n-1)-цикла. Числовое обозначение колёс в литературе не устоялось — некоторые авторы используют n для обозначения длины цикла, так что их W_n означает граф W_n+1 по определению выше. Колесо может быть определено также, как 1-скелет (n-1)-угольной пирамиды.

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

Граф Мёбиуса — Кантора — симметричный двудольный кубический граф с 16 вершинами и 24 рёбрами, названный в честь Августа Фердинанда Мёбиуса и Зелигмана Кантора (1857—1903). Его можно определить как обобщённый граф Петерсена $\text{[math]}$ , то есть он образован вершинами восьмиугольника, соединёнными с восьмиугольной звездой, в которой каждая точка соединена с третьей по счёту точкой.

В теории графов графом Паппа называется двудольный 3-регулярный неориентированный граф с 18 вершинами и 27 рёбрами, являющийся графом Леви конфигурации Паппа. Он назван в честь Паппа Александрийского, математика Древней Греции, который верил, что доказал «теорему о шестиугольнике», в которой описывал конфигурацию Паппа. Все кубические дистанционно-регулярные графы известны. Граф Паппа — один из тринадцати таких графов.

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

Куби́ческий граф — граф, в котором все вершины имеют степень три. Другими словами, кубический граф является 3-регулярным. Кубические графы называются также тривалентными.

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

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

Граф Коксетера — 3-регулярный граф с 28 вершинами и 42 рёбрам Все кубические дистанционно-регулярные графы известны, граф Коксетера — один из 13-ти таких графов.

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

В теории графов граф Науру — это симметричный двудольный кубический граф с 24 вершинами и 36 рёбрами. Граф был назван Дэвидом Эпштейном по аналогии с двенадцатилучевой звездой на флаге Науру.

В теории графов лестница L_n — планарный неориентированный граф с 2n вершинами и n+2(n-1) рёбрами.

Граф F26A — симметричный двудольный кубический граф с 26 вершинами и 39 рёбрами.

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

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

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

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

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

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