Граф Мёбиуса — Кантора (Ijgs B~Qnrvg — Tgumkjg)

Граф Мёбиуса – Кантора
Граф Мёбиуса – Кантора
Назван в честь	Август Фердинанд Мёбиус и З. Кантор
Вершин	16
Рёбер	24
Радиус	4
Диаметр	4
Обхват	6
Автоморфизмы	96
Хроматическое число	2
Хроматический индекс	3
Род	1
Свойства	симметричный; гамильтонов; двудольный; кубический; единичных расстояний; граф Кэли; совершенный; просто ориентируем

Граф Мёбиуса — Кантора — симметричный двудольный кубический граф с 16 вершинами и 24 рёбрами, названный в честь Августа Фердинанда Мёбиуса и Зелигмана Кантора (1857—1903). Его можно определить как обобщённый граф Петерсена $G(8,3)$ , то есть он образован вершинами восьмиугольника, соединёнными с восьмиугольной звездой, в которой каждая точка соединена с третьей по счёту точкой.

Конфигурация Мёбиуса — Кантора

Мёбиус в 1828 году^[1] поставил вопрос о существовании пары многоугольников с $p$ сторонами в каждом, обладающих свойством, что вершины одного многоугольника лежат на прямых, проходящих через стороны другого, и наоборот. Если такая пара существует, то вершины и стороны этих многоугольников должны образовывать проективную конфигурацию. Для $p=4$ не существует решения на евклидовой плоскости, но в 1882 году Кантор^[2] нашёл пару многоугольников такого типа в обобщении задачи, в котором точки и рёбра принадлежат комплексной проективной плоскости, то есть в решении Кантора координатами вершин многоугольника являются комплексные числа. Решение Кантора для $p=4$ — пара взаимно вписанных четырёхугольников на комплексной проективной плоскости, называется конфигурацией Мёбиуса — Кантора. Граф Мёбиуса — Кантора получил своё имя от конфигурации Мёбиуса — Кантора, поскольку он является графом Леви этой конфигурации. Граф имеет одну вершину для каждой точки конфигурации и по точке для каждой тройки, а рёбра соединяют две вершины, если одна вершина соответствует точке, а другая — тройке, содержащей эту точку.

Связь с гиперкубом

Граф Мёбиуса — Кантора является подграфом четырёхмерного графа гиперкуба и образован путём удаления восьми рёбер из гиперкуба^[3]. Поскольку гиперкуб является графом единичных расстояний, граф Мёбиуса — Кантора можно тоже изобразить на плоскости со всеми сторонами единичной длины, хотя такое представление приведёт к появлению перекрещивающихся рёбер.

Топология

Граф Мёбиуса — Кантора нельзя вложить в плоскость без пересечений, его число скрещиваний равно 4, и он является наименьшим кубическим графом с таким числом скрещиваний^[4]. Кроме того, граф даёт пример графа, все подграфы которого имеют число пересечений на два и более отличающихся от числа пересечений самого графа^[5]. Однако он является тороидальным — существует его вложение в тор, при котором все его грани являются шестиугольниками^[6]. Двойственный граф этого вложения — это граф гипероктаэдра $K_{2,2,2,2}$ .

Существует даже более симметричное вложение графа Мёбиуса — Кантора в двойной тор^[англ.], являющееся правильной картой и имеющее шесть восьмиугольных граней, в котором все 96 симметрий графа можно осуществить как симметрии вложения^[7]. 96-элементную группу симметрии вложения имеет граф Кэли, который может быть вложен в двойной тор. В 1984 году показано, что это единственная группа рода два^[8].

Скульптура Девитта Годфри (DeWitt Godfrey) и Дуэйна Мартинеса (Duane Martinez) в виде двойного тора с вложенным графом Мёбиуса — Кантора выставлялась в Техническом музее Словении на шестой Словенской международной конференции по теории графов в 2007 году. В 2013 году вращающаяся версия скульптуры была выставлена в Колгейтском университете.

Граф Мёбиуса — Кантора допускает вложение в тройной тор^[англ.] (тор третьего рода), которое даёт правильную карту, имеющую четыре 12-угольных грани^[6].

В 2004 году в рамках исследования возможных химических углеродных структур, изучено семейство всех вложений графа Мёбиуса — Кантора в двумерные многообразия, в результате показано, что существует 759 неэквивалентных вложений^[9].

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

Группа автоморфизмов графа Мёбиуса — Кантора — это группа порядка 96^[10]. Она действует транзитивно на вершины и на рёбра, поэтому граф Мёбиуса — Кантора является симметричным. У него есть автоморфизмы, которые переводят любую вершину в любую другую и любое ребро в любое другое. Согласно списку Фостера граф Мёбиуса — Кантора является единственным симметричным графом с 16 вершинами и наименьшим кубическим симметричным графом, который не является дистанционно-транзитивным^[11]. Граф Мёбиуса — Кантора является также графом Кэли.

Обобщённый граф Петерсена $G(n,k)$ является вершинно-транзитивным в том и только в том случае, когда $n=10$ и $k=2$ , или когда $k^{2}=\pm 1{\pmod {n}}$ , и рёберно-транзитивным только в следующих семи случаях: $(n,k)\in \{(4,1),(5,2),(8,3),(10,2),(10,3),(12,5),(24,5)\}$ ^[12]. Таким образом, граф Мёбиуса — Кантора является одним из этих семи ребёрно-транзитивных обобщённых графов Петерсена. Его симметричное вложение в двойной тор — одна из семи правильных кубических карт, для которых общее число вершин вдвое больше числа вершин граней^[13]. Среди семи симметричных обобщённых графов Петерсена находятся кубический граф $G(4,1)$ , граф Петерсена $G(5,2)$ , граф додекаэдра $G(10,2)$ , граф Дезарга $G(10,3)$ и граф Науру $G(12,5)$ .

Характеристический многочлен графа Мёбиуса — Кантора равен:

(x-3)(x-1)^{3}(x+1)^{3}(x+3)(x^{2}-3)^{4}.\

Примечания

↑ Мёбиус, 1828.
↑ Кантор, 1882.
↑ Коксетер, 1950.
↑ последовательность A110507 в OEIS
↑ Dan McQuillan, R. Bruce Richter. On the crossing numbers of certain generalized Petersen graphs // Discrete Mathematics. — 1992. — Т. 104, вып. 3. — С. 311–320. — doi:10.1016/0012-365X(92)90453-M.
↑ ¹ ² Марушич, Писанский, 2000.
↑ Трелфол, 1932.
↑ Такер, 1984.
↑ Лейнен, Куэльманс, 2004.
↑ Royle, G. F016A data (недоступная ссылка)
↑ Conder, M.^[англ.], Dobcsányi, P. «Trivalent Symmetric Graphs Up to 768 Vertices.» J. Combin. Math. Combin. Comput. 40, 41-63, 2002
↑ Фрухт, Грейвер, Уоткинс, 1971.
↑ Макмюллен, 1992.

Ссылки

H. S. M. Coxeter. Self-dual configurations and regular graphs // Bulletin of the American Mathematical Society. — 1950. — Т. 56, вып. 5. — С. 413–455. — doi:10.1090/S0002-9904-1950-09407-5.
R. Frucht, J. E. Graver, M. E. Watkins. The groups of the generalized Petersen graphs // Proceedings of the Cambridge Philosophical Society. — 1971. — Т. 70, вып. 02. — С. 211–218. — doi:10.1017/S0305004100049811.
S. Kantor. Über die Configurationen (3, 3) mit den Indices 8, 9 und ihren Zusammenhang mit den Curven dritter Ordnung // Sitzungsberichte der Mathematisch-Naturwissenschaftlichen Classe der Kaiserlichen Akademie der Wissenschaften, Wien. — 1882. — Т. 84, вып. 1. — С. 915–932..
E. Lijnen, A. Ceulemans. Oriented 2-Cell Embeddings of a Graph and Their Symmetry Classification: Generating Algorithms and Case Study of the Möbius-Kantor Graph // J. Chem. Inf. Comput. Sci.. — 2004. — Т. 44, вып. 5. — С. 1552–1564. — doi:10.1021/ci049865c. — PMID 15446812.
Dragan Marušič, Tomaž Pisanski. The remarkable generalized Petersen graph G(8,3) // Math. Slovaca. — 2000. — Т. 50. — С. 117–121.
Peter McMullen. The regular polyhedra of type {p, 3} with 2p vertices // Geometriae Dedicata. — 1992. — Т. 43, вып. 3. — С. 285–289. — doi:10.1007/BF00151518.
A. F. Möbius. Kann von zwei dreiseitigen Pyramiden eine jede in Bezug auf die andere um- und eingeschrieben zugleich heissen? // J. Reine Angew. Math.. — 1828. — Т. 3. — С. 273–278.. В Gesammelte Werke (1886), том 1, страницы 439—446.
Thomas W. Tucker. There is only one group of genus two // Journal of Combinatorial Theory, Series B. — 1984. — Т. 36, вып. 3. — С. 269–275. — doi:10.1016/0095-8956(84)90032-7.
W. Threlfall. Gruppenbilder // Abhandlungen der Mathematisch-Physischen Klasse der Sächsischen Akademie der Wissenschaften. — 1932. — Т. 41, вып. 6. — С. 1–59..
Unveiling of the sculpture.

Внешние ссылки

Weisstein, Eric W. Möbius-Kantor Graph (англ.) на сайте Wolfram MathWorld.
Weisstein, Eric W. Möbius-Kantor Configuration (англ.) на сайте Wolfram MathWorld.

[_36fc121b739a25cf-1] Мёбиус, 1828.

[_5e76648041e7692d-2] Кантор, 1882.

[_47cc50be202a3d0a-3] Коксетер, 1950.

[4] последовательность A110507 в OEIS

[5] Dan McQuillan, R. Bruce Richter. On the crossing numbers of certain generalized Petersen graphs // Discrete Mathematics. — 1992. — Т. 104, вып. 3. — С. 311–320. — doi:10.1016/0012-365X(92)90453-M.

[_d2d89bc312ed4c8c-6] ¹ ² Марушич, Писанский, 2000.

[_d687a391aa1af687-7] Трелфол, 1932.

[_15f57e2f911457d1-8] Такер, 1984.

[_debf379a8461b9d4-9] Лейнен, Куэльманс, 2004.

[10] Royle, G. F016A data (недоступная ссылка)

[COND-11] Conder, M.^[англ.], Dobcsányi, P. «Trivalent Symmetric Graphs Up to 768 Vertices.» J. Combin. Math. Combin. Comput. 40, 41-63, 2002

[_e85c550df9470ae4-12] Фрухт, Грейвер, Уоткинс, 1971.

[_040b2e2732ab296f-13] Макмюллен, 1992.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]