График Мёбиуса – Кантора - Möbius–Kantor graph

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

в математический поле теория графов, то График Мёбиуса – Кантора это симметричный двудольный кубический граф с 16 вершинами и 24 ребрами названных в честь Август Фердинанд Мёбиус и Селигманн Кантор. Его можно определить как обобщенный граф Петерсена грамм(8,3): то есть он образован вершинами восьмиугольник, соединенный с вершинами восьмиконечной звезды, в которой каждая точка звезды соединена с точками на расстоянии трех шагов от нее.

Конфигурация Мебиуса – Кантора

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

Мебиус (1828) спросил, существует ли пара полигоны с п стороны каждой, обладающие тем свойством, что вершины одного многоугольника лежат на линиях, проходящих через края другого многоугольника, и наоборот. Если это так, то вершины и ребра этих многоугольников образуют проективная конфигурация. За п = 4 нет решения в Евклидова плоскость, но Кантор (1882) найденные пары многоугольников этого типа для обобщения задачи, в которой точки и ребра принадлежат комплексная проективная плоскость. То есть в решении Кантора координаты вершин многоугольника равны сложные числа. Кантора для п = 4, пара вписанных друг в друга четырехугольников в комплексной проективной плоскости, называется Конфигурация Мебиуса – Кантора. Граф Мёбиуса-Кантора получил свое название от Граф Леви конфигурации Мёбиуса – Кантора. Он имеет одну вершину на точку и одну вершину на тройку, причем ребро соединяет две вершины, если они соответствуют точке и тройке, содержащей эту точку.

Конфигурация также может быть описана алгебраически в терминах абелева группа ${displaystyle mathbb {Z} _ {3} imes mathbb {Z} _ {3}}$ с девятью элементами, в этой группе четыре подгруппы третьего порядка (подмножества элементов вида ${displaystyle (i, 0)}$ , ${displaystyle (i, i)}$ , ${displaystyle (i, 2i)}$ , и ${displaystyle (0, i)}$ соответственно), каждый из которых может быть использован для разделения девяти элементов группы на три смежные классы из трех элементов на смежный класс. Эти девять элементов и двенадцать смежных классов образуют конфигурацию, Конфигурация Гессен. Удаление нулевого элемента и четырех смежных классов, содержащих ноль, приводит к конфигурации Мёбиуса – Кантора.

Как подграф

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

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

Топология

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

Граф Мебиуса – Кантора нельзя вложить в плоскость без пересечений; она имеет номер перехода 4, и является наименьшим кубическим графом с этим числом пересечения (последовательность A110507 в OEIS ). Кроме того, он предоставляет пример графа, номера пересечения всех подграфов которого отличаются от него на два или более.^[1]Однако это тороидальный граф: он имеет вложение в тор в котором все лица шестиугольники (Марушич и Писанский 2000 ). В двойственный граф этого вложения является гипероктаэдрический граф K_2,2,2,2.

Существует еще более симметричное вложение графа Мёбиуса – Кантора в двойной тор который является обычная карта, с шестью восьмиугольный грани, в которых все 96 симметрий графа могут быть реализованы как симметрии вложения; Кокстер (1950) приписывает это вложение Трелфолл (1932). Его 96-элементный группа симметрии имеет Граф Кэли которое само может быть вложено в двойной тор, и было показано Такер (1984) быть уникальной группой с род два. Граф Кэли с 96 вершинами - это флаговый граф регулярного отображения рода 2, имеющий граф Мёбиуса – Кантора в качестве каркаса. Это означает, что его можно получить из регулярной карты как каркас двойственного к ее барицентрическому подразделению. Скульптура ДеВитт Годфри и Дуэйн Мартинес показывающая двойное вложение симметрий графа Мёбиуса – Кантора в тор, была открыта в Техническом музее г. Словения в рамках 6-й словенской международной конференции по теории графов в 2007 году. В 2013 году вращающаяся версия скульптуры была представлена на Колгейтский университет.

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

Lijnen & Ceulemans (2004), мотивированный исследованием потенциальных химических структур углеродных соединений, изучил семейство всех вложений графа Мебиуса – Кантора на 2-коллекторы; они показали, что существует 759 неэквивалентных вложений.

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

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

Обобщенный граф Петерсена грамм(п, к) вершинно-транзитивно тогда и только тогда, когда п = 10 и k = 2 или если k² ≡ ± 1 (мод.п) и является реберно-транзитивным только в следующих семи случаях: (п, к) = (4,1), (5,2), (8,3), (10,2), (10,3), (12,5) или (24,5) (Frucht, Graver & Watkins, 1971 г. ). Итак, граф Мёбиуса – Кантора - один из семи симметричных обобщенных графов Петерсена. Его симметричное двойное вложение тора, соответственно, является одним из семи регулярных кубических отображений, в которых общее число вершин в два раза больше числа вершин на грани (Макмаллен 1992 ). Среди семи симметричных обобщенных графов Петерсена есть кубический график ${displaystyle G (4,1)}$ , то Граф Петерсена ${displaystyle G (5,2)}$ , то додекаэдрический граф ${displaystyle G (10,2)}$ , то График дезарга ${displaystyle G (10,3)}$ и Науру график ${displaystyle G (12,5)}$ .

В характеристический многочлен графа Мёбиуса – Кантора равно

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

Смотрите также

Группа Паули

Примечания

^ Маккуиллан, Дэн; Рихтер, Р. Брюс (1992), "О числах пересечения некоторых обобщенных графов Петерсена", Дискретная математика, 104 (3): 311–320, Дои:10.1016 / 0012-365X (92) 90453-М, МИСТЕР 1171327.
^ Ройл, Г. F016A данные^{[постоянная мертвая ссылка ]}
^ Кондер, М. и Добчани П. «Трехвалентные симметричные графы до 768 вершин». J. Combin. Математика. Комбинировать. Comput. 40, 41-63, 2002.

внешняя ссылка

[1] Маккуиллан, Дэн; Рихтер, Р. Брюс (1992), "О числах пересечения некоторых обобщенных графов Петерсена", Дискретная математика, 104 (3): 311–320, Дои:10.1016 / 0012-365X (92) 90453-М, МИСТЕР 1171327.

[2] Ройл, Г. F016A данные^{[постоянная мертвая ссылка ]}

[COND-3] Кондер, М. и Добчани П. «Трехвалентные симметричные графы до 768 вершин». J. Combin. Математика. Комбинировать. Comput. 40, 41-63, 2002.

[1]

[2]

[3]