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

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

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

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

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

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

Характеристический многочлен графа МакГи равен ${\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.
• 
  Альтернативное изображение графа МакГи.

Примечания