Граф МакГи

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

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

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

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

Граф МакГи имеет радиус 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 − 4 x − 2 ) 4 {displaystyle 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. Граф МакГи — это наименьшая кубическая клетка, не являющаяся вершинно-транзитивной.

Галерея

• Число пересечений графа МакГи равно 8.

• Хроматическое число графа МакГи равно 3.

• Хроматический индекс графа МакГи ракен 3.

• The Ациклический хроматический индекс графа МакГи равен 3.

• Альтернативное изображение графа МакГи.