Граф Мёбиуса — Кантора

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

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

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

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

Топология 

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

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

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

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

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

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

Обобщённый граф Петерсена  является вершинно-транзитивным в том и только в том случае, когда  и , или когда , и рёберно-транзитивным только в следующих семи случаях: . Таким образом, граф Мёбиуса — Кантора является одним этих семи ребёрно-транзитивных обобщённых графов Петерсена. Его симметричное вложение в двойной тор — одна из семи правильных кубических карт, для которых общее число вершин вдвое больше числа вершин граней. Среди семи симметричных обобщённых графов Петерсена находятся кубический граф , граф Петерсена , граф додекаэдра , граф Дезарга  и граф Науру .

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

Примечания

Ссылки 
 
 
 .
 
 
 
 . В Gesammelte Werke (1886), том 1, страницы 439—446.
 
 .

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

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