В математической области теории графов , то граф Мебиуса-Кантор является симметричный двудольный кубический граф с 16 вершинами и 24 ребрами имени Август Фердинанд Мёбиус и Seligmann Кантор . Его можно определить как обобщенный граф Петерсена G (8,3): то есть он образован вершинами восьмиугольника , соединенными с вершинами восьмиконечной звезды, в которой каждая точка звезды соединена с указывает в трех шагах от него.
Граф Мебиуса – Кантора | |
---|---|
Названный в честь | Август Фердинанд Мебиус и С. Кантор |
Вершины | 16 |
Края | 24 |
Радиус | 4 |
Диаметр | 4 |
Обхват | 6 |
Автоморфизмы | 96 |
Хроматическое число | 2 |
Хроматический индекс | 3 |
Род | 1 |
Толщина книги | 3 |
Номер очереди | 2 |
Характеристики | Симметричный гамильтониан Двудольные кубические единичные расстояния Граф Кэли Совершенный ориентированно простой |
Таблица графиков и параметров |
Конфигурация Мебиуса – Кантора
Мебиус (1828) спросил, существует ли пара многоугольников с p сторонами каждый, обладающих тем свойством, что вершины одного многоугольника лежат на прямых, проходящих через края другого многоугольника, и наоборот. Если это так, то вершины и ребра этих многоугольников образуют проективную конфигурацию . При p = 4 нет решения на евклидовой плоскости , но Кантор (1882) нашел пары многоугольников этого типа для обобщения задачи, в которой точки и ребра принадлежат комплексной проективной плоскости . То есть в решении Кантора координаты вершин многоугольника - комплексные числа . Решение Кантора для p = 4, пара вписанных друг в друга четырехугольников в комплексной проективной плоскости, называется конфигурацией Мёбиуса – Кантора . Граф Мёбиуса-Кантора получил свое название от графа Леви конфигурации Мёбиуса-Кантора. Он имеет одну вершину на точку и одну вершину на тройку, причем ребро соединяет две вершины, если они соответствуют точке и тройке, содержащей эту точку.
Конфигурация также может быть описана алгебраически в терминах абелевой группы с девятью элементами. В этой группе четыре подгруппы третьего порядка (подмножества элементов вида, , , а также соответственно), каждый из которых может использоваться для разделения девяти элементов группы на три смежных класса по три элемента в каждом смежном классе. Эти девять элементов и двенадцать смежных классов образуют конфигурацию, конфигурацию Гессе . Удаление нулевого элемента и четырех смежных классов, содержащих ноль, приводит к конфигурации Мёбиуса – Кантора.
Как подграф
Граф Мебиуса – Кантора - это подграф четырехмерного графа гиперкуба , образованный удалением восьми ребер из гиперкуба ( Coxeter 1950 ). Поскольку гиперкуб является графом единичных расстояний, граф Мёбиуса – Кантора также может быть нарисован на плоскости со всеми ребрами единичной длины, хотя такой чертеж обязательно будет иметь несколько пар пересекающихся ребер.
Граф Мёбиуса – Кантора также встречается много раз, как в индуцированном подграфе графа Хоффмана – Синглтона . Каждый из этих экземпляров фактически является собственным вектором графа Хоффмана-Синглтона с соответствующим собственным значением -3. Каждая вершина, не входящая в индуцированный граф Мёбиуса-Кантора, смежна ровно с четырьмя вершинами в графе Мёбиуса-Кантора, по две в каждой половине двудольного графа Мёбиуса-Кантора.
Топология
Граф Мёбиуса – Кантора не может быть вложен в плоскость без пересечений; он имеет номер пересечения 4 и является наименьшим кубическим графом с этим номером пересечения (последовательность A110507 в OEIS ). Кроме того, он предоставляет пример графа, номера пересечения всех подграфов которого отличаются от него на два или более. [1] Однако это тороидальный граф : он имеет вложение в тор, в котором все грани являются шестиугольниками ( Marušič & Pisanski 2000 ). Двойственный граф этого вложения является гипероктаэдральным графом К 2,2,2,2 .
Существует еще более симметричное вложение графа Мёбиуса – Кантора в двойной тор, который является регулярным отображением с шестью восьмиугольными гранями, в котором все 96 симметрий графа могут быть реализованы как симметрии вложения; Коксетер (1950) приписывает это вложение Трелфоллу (1932) . Ее 96-элементная группа симметрии имеет граф Кэли, который сам может быть вложен в двойной тор, и Такер (1984) показал, что это единственная группа с родом два. Граф Кэли на 96 вершинах является флаговым графом регулярного отображения рода 2, имеющим граф Мёбиуса – Кантора в качестве скелета. Это означает, что его можно получить из регулярной карты как каркас двойственного к ее барицентрическому подразделению. Скульптура ДеВитта Годфри и Дуэйна Мартинеса, показывающая вложение симметрий графа Мебиуса – Кантора в двойной тор, была открыта в Техническом музее Словении в рамках 6-й словенской международной конференции по теории графов в 2007 году. скульптура была открыта в университете Колгейт .
Граф Мёбиуса – Кантора допускает вложение в тройной тор ( тор рода 3), который является регулярным отображением с четырьмя 12-угольными гранями и является двойственным по Петри вложению двойного тора, описанного выше; ( Марушич и Писанский, 2000 ).
Lijnen & Ceulemans (2004) , мотивированные исследованием потенциальных химических структур углеродных соединений, изучили семейство всех вложений графа Мебиуса – Кантора на двумерные многообразия ; они показали, что существует 759 неэквивалентных вложений.
Алгебраические свойства
Группа автоморфизмов графа Мёбиуса – Кантора - это группа порядка 96. [2] Она действует транзитивно на вершинах, на ребрах и на дугах графа. Следовательно, граф Мёбиуса – Кантора является симметричным графом . У него есть автоморфизмы, которые переводят любую вершину в любую другую вершину и любое ребро в любое другое ребро. Согласно переписи населения Фостера , граф Мебиуса – Кантора является уникальным кубическим симметричным графом с 16 вершинами и наименьшим кубическим симметричным графом, который также не является дистанционно-транзитивным . [3] Граф Мёбиуса – Кантора также является графом Кэли .
Обобщенный граф Петерсена G ( n, k ) является вершинно-транзитивным тогда и только тогда, когда n = 10 и k = 2 или если k 2 ≡ ± 1 (mod n ), и является реберно-транзитивным только в следующих семи случаях: ( n , k ) = (4,1), (5,2), (8,3), (10,2), (10,3), (12,5) или (24,5) ( Frucht, Graver И Уоткинс 1971 ). Таким образом, граф Мебиуса – Кантора - один из семи симметричных обобщенных графов Петерсена. Его симметричное двойное вложение тора, соответственно, является одним из семи регулярных кубических отображений, в которых общее число вершин в два раза больше числа вершин на грани ( McMullen, 1992 ). Среди семи симметричных обобщенных графов Петерсена есть кубический граф , граф Петерсена , додекаэдрический граф , граф Дезарга и граф Науру .
Характеристический полином графа Мебиуса-Кантор равно
Смотрите также
- Группа Паули
Заметки
- ^ Маккуиллан, Дэн; Рихтер, Р. Брюс (1992), "О числах пересечения некоторых обобщенных графов Петерсена", Дискретная математика , 104 (3): 311–320, DOI : 10.1016 / 0012-365X (92) 90453-M , MR 1171327.
- ^ Ройл, Г. Данные F016A [ постоянная мертвая ссылка ]
- ^ Кондер, М. и Добчаньи, П. "Трехвалентные симметричные графы до 768 вершин". J. Combin. Математика. Комбинировать. Comput. 40, 41-63, 2002.
Рекомендации
- Косетер, HSM (1950), "Автодуальные конфигурации и регулярные графы", Бюллетень Американского математического общества , 56 (5): 413-455, DOI : 10,1090 / S0002-9904-1950-09407-5.
- Фрухт, Роберт ; Гравер, Джек Э .; Уоткинс, Марк Е. (1971), "Группы обобщенных графов Петерсена", Труды Кембриджского философского общества , 70 (02): 211-218, DOI : 10,1017 / S0305004100049811 , MR 0289365.
- Кантор, Seligmann (1882), "Убер умереть Configurationen (3, 3) мит ден Индексы 8, 9 унд Ihren Zusammenhang мит ден Curven dritter Ordnung", Sitzungsberichte дер Mathematisch-Naturwissenschaftlichen Классе дер Kaiserlichen Akademie дер Wissenschaften, Wien , 84 (1) : 915–932.
- Lijnen, Erwin; Ceulemans, Arnout (2004), "Ориентированные двухэлементные вложения графа и их классификация симметрии: создание алгоритмов и тематическое исследование графа Мебиуса-Кантора", Журнал химической информации и моделирования , 44 (5): 1552–1564, DOI : 10.1021 / ci049865c , PMID 15446812.
- Марушич, Драган ; Писанский, Томаж (2000), "Замечательный обобщенный граф Петерсена G (8,3)" , Mathematica Slovaca , 50 : 117–121.
- МакМаллен, Питер (1992), «Правильные многогранники типа { p , 3} с 2 p вершинами», Geometriae Dedicata , 43 (3): 285–289, doi : 10.1007 / BF00151518.
- Мёбиус, Август Фердинанд (1828), «Kann von zwei dreiseitigen Pyramiden eine jede in Bezug auf die andere um- und eingeschrieben zugleich heissen?» (PDF) , Journal für die reine und angewandte Mathematik , 3 : 273–278. В Gesammelte Werke (1886), т. 1. С. 439–446.
- Tucker, Thomas W. (1984), "Существует только одна группа рода два", Журнал комбинаторной теории, серии B , 36 (3): 269-275, DOI : 10,1016 / 0095-8956 (84) 90032-7.
- Трелфолл, Уильям (1932), "Gruppenbilder", Abhandlungen der Mathematisch-Physischen Klasse der Sächsischen Akademie der Wissenschaften , 41 (6): 1–59.
- Джессика Вольц, Разработка линейных макетов с помощью SAT. Магистерская работа, Тюбингенский университет, 2018 г.
Внешние ссылки
- Вайсштейн, Эрик В. «График Мёбиуса-Кантора» . MathWorld .
- Открытие скульптуры университета Колгейт