Граф МакГи

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

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

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

Известны наименьшие кубические графы с числом скрещиваний 1—8 (Шаблон: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-4x-2{)}^4$.

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

Галерея

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