В математической области теории графов , в графе McGee или (3-7) -cage представляет собой 3- регулярный граф с 24 вершинами и 36 ребрами. [1]
График Макги | |
---|---|
Названный в честь | У. Ф. МакГи |
Вершины | 24 |
Края | 36 |
Радиус | 4 |
Диаметр | 4 [1] |
Обхват | 7 [1] |
Автоморфизмы | 32 [1] |
Хроматическое число | 3 [1] |
Хроматический индекс | 3 [1] |
Толщина книги | 3 |
Номер очереди | 2 |
Характеристики | Гамильтониан кубической клетки |
Таблица графиков и параметров |
Граф МакГи - это единственная (3,7) -клетка (наименьший кубический граф обхвата 7). Это также самая маленькая кубическая клетка, которая не является графом Мура .
Впервые обнаруженный Саксом, но не опубликованный [2], граф назван в честь Макги, опубликовавшего результат в 1960 году. [3] Затем граф МакГи был доказан Тюттом как уникальная (3,7) -клетка в 1966 году [4]. [5] [6]
Граф МакГи требует как минимум восьми пересечений на любом его чертеже на плоскости. Это один из пяти неизоморфных графов, связанных как наименьший кубический граф, требующий восьми пересечений. Другой из этих пяти графов - это обобщенный граф Петерсена G (12,5) , также известный как граф Науру . [7] [8]
Граф МакГи имеет радиус 4, диаметр 4, хроматическое число 3 и хроматический индекс 3. Это также 3- вершинно-связный и 3 -реберный граф. Он имеет книжную толщину 3 и номер очереди 2. [9]
Алгебраические свойства
Характеристический полином графа McGee является
- .
Группа автоморфизмов графа МакГи имеет порядок 32 и не действует транзитивно на свои вершины: есть две вершинные орбиты длиной 8 и 16. Граф МакГи - это наименьшая кубическая клетка, которая не является вершинно-транзитивным графом . [10] [ нужен лучший источник ]
Галерея
Число пересечений графа МакГи - 8.
Хроматическим числом графа McGee равно 3.
Хроматической индекс графа McGee равен 3.
Ациклическое хроматическое число графа McGee равно 3.
Альтернативный рисунок графа МакГи.
Рекомендации
- ^ a b c d e f Вайсштейн, Эрик В. «График МакГи» . MathWorld .
- ^ Kárteszi, F. "Piani finit ciclici приходят risoluzioni ди ип Certo problemo ди Minimo." Болл. ООН. Мат. Ital. 15, 522-528, 1960
- ^ Макги, У. Ф. «Минимальный кубический граф седьмого обхвата». Канад. Математика. Бык. 3, 149–152, 1960 г.
- ^ Тутте, В. Т. Связность в графиках. Торонто, Онтарио: Университет Торонто Press, 1966 г.
- ^ Вонг, П.К. «Клетки - обзор». J. Graph Th. 6, 1-22, 1982 г.
- ^ Брауэр, AE; Коэн, AM; и Ноймайер, А. Дистанционные регулярные графы. Нью-Йорк: Springer-Verlag, стр. 209, 1989 г.
- ^ Слоан, Н. Дж. А. (ред.). «Последовательность A110507 (Количество узлов в наименьшем кубическом графе с номером пересечения n)» . Он -лайн энциклопедия целочисленных последовательностей . Фонд OEIS.
- ^ Пегг, ET ; Эксу, Г. (2009), "Графики числа пересечений" , Mathematica Journal , 11.
- ^ Джессика Wolz, Инженерная Линейные Макеты с SAT . Магистерская работа, Тюбингенский университет, 2018 г.
- ^ Бонди, Дж. А. и Мерти, Теория графов USR с приложениями. Нью-Йорк: Северная Голландия, стр. 237, 1976.