Граф МакГи

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

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

Впервые открытый , но не опубликованныйKárteszi, F. «Piani finit ciclici come risoluzioni di un certo problemo di minimo.» Boll. Un. Mat. Ital. 15, 522—528, 1960, граф назван в честь МакГи (W. F. McGee), который опубликовал результат в 1960 годуMcGee, W. F. «A Minimal Cubic Graph of Girth Seven.» Canad. Math. Bull. 3, 149—152, 1960. Позднее, в 1966 году, Уильям Томас Татт доказал, что это единственная (3,7)-клеткаTutte, W. T. Connectivity in Graphs. Toronto, Ontario: University of Toronto Press, 1966Wong, P. K. «Cages--A Survey.» J. Graph Th. 6, 1-22, 1982Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance Regular Graphs. New York: Springer-Verlag, p. 209, 1989.

Известны наименьшие кубические графы с числом скрещиваний 1—8 (), наименьший граф с числом скрещиваний 8 — это граф МакГи. Существует 5 неизоморфных кубических графов порядка 24 с числом скрещиваний 8Pegg, E. T. and Exoo, G. «Crossing Number Graphs.» Mathematica J. 11, 2009, один из них — обобщённый граф Петерсена G(12,5), известный также как Граф Науру.

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

Алгебраические свойства Характеристический многочлен графа МакГи равен .

Автоморфизм группы графа МакГи имеет порядок 32 и не транзитивен относительно вершин — имеется две орбиты вершин длины 8 и 16. Граф МакГи — это наименьшая кубическая клетка, не являющаяся вершинно-транзитивнойBondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 237, 1976..

Галерея

Примечания

Категория:Регулярные графы Категория:Графы, имеющие собственные названия