Граф Маꥳ

Граф МакЖі — це єдина (3,7) клітка (найменший кубічний з обхватом 7). Він є найменшою кубічної кліткою, яка не є графом Мура.

В теорії графів графом МакЖі, або (3-7)-клітиною, називається 3-регулярний граф з 24 вершинами і 36 ребрами. Вперше відкритий Хорстом Саксом, але не опублікований, граф названий на честь МакЖі (англ. 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}-4x-2)^{4}$.

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

Галерея

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