Граф Маꥳ

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

В теорії графів графом МакЖі, або (3-7)-клітиною, називається 3-регулярний граф з 24 вершинами і 36 ребрами[1]. Вперше відкритий Хорстом Саксом, але не опублікований[2][3], граф названий на честь МакЖі (англ. W. F. McGee), який опублікував результат в 1960 році. Пізніше, в 1966 році, Вільям Томас Татт довів, що це єдина (3,7)-клітина.

Відомі найменші кубічні графи з числом схрещень 1-8 (послідовність A110507 в OEIS), найменший граф з числом схрещень 8 - це граф МакГі. Існує 5 неізоморфних кубічних графів порядку 24 з числом схрещень 8, один з них - узагальнений граф Петерсена G (12,5), відомий також як Граф Науру.

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

Алгебраїчні властивості

[ред. | ред. код]

Характеристичний многочлен графа МакЖі дорівнює .

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

Галерея

[ред. | ред. код]

Примітки

[ред. | ред. код]
  1. Архівована копія. Архів оригіналу за 18 жовтня 2016. Процитовано 17 жовтня 2016.{{cite web}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title (посилання)
  2. Kárteszi, F. "Piani finit ciclici come risoluzioni di un certo problemo di minimo." Boll. Un. Mat. Ital. 15, 522-528, 1960
  3. McGee, W. F. "A Minimal Cubic Graph of Girth Seven." Canad. Math. Bull. 3, 149-152, 1960