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

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

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

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

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

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

В качестве подграфа

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

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

Топология

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

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

Граф Мёбиуса – Кантора допускает вложение в тройной тор (тор рода 3), который представляет собой регулярное отображение с четырьмя 12-угольными гранями и является двойственным по Петри вложению двойного тора, описанному выше. ^{[ 4 ]}

Лийнен и Сеулеманс (2004) , движимые исследованием потенциальных химических структур углеродных соединений, изучили семейство всех вложений графа Мёбиуса-Кантора в 2- многообразия ; они показали, что существует 759 неэквивалентных вложений. Вложение рода 1, которое не является обычным отображением, показано на диаграмме выше.

Встраивание рода 2
Встраивание рода 3

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

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

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

Характеристический полином графа Мёбиуса–Кантора равен ^{[ 9 ]}

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

Граф Мёбиуса–Кантора представляет собой двойное покрытие графика куба. ^{[ 1 ]}

См. также

Группа Паули , чей граф Кэли является графом Мёбиуса-Кантора.

Примечания

^ Перейти обратно: ^а ^б Коксетер 1950 .
^ OEIS A110507 Последовательность
^ Маккуиллан и Рихтер 1992 .
^ Перейти обратно: ^а ^б ^с Марушич и Писански 2000 .
^ Коксетер (1950) приписывает это встраивание Трелфоллу (1932) .
^ Кондер и Добчани 2002 .
^ Фрухт, Грейвер и Уоткинс 1971 .
^ Макмаллен 1992 .
^ Брауэр, Эндрю Э. «График Мёбиуса-Кантора» . www.win.tue.nl. Проверено 21 июля 2024 г.

Ссылки

Кондер, Марстон ; Добчаньи, Питер (2002), «Трехвалентные симметричные графы с числом вершин до 768», Журнал комбинаторной математики и комбинаторных вычислений , 40 : 41–63, MR 1887966 .
Коксетер, HSM (1950), «Самодвойственные конфигурации и регулярные графы», Бюллетень Американского математического общества , 56 (5): 413–455, doi : 10.1090/S0002-9904-1950-09407-5 .
Фрухт, Роберт ; Грейвер, Джек Э.; Уоткинс, Марк Э. (1971), «Группы обобщенных графов Петерсена», Proceedings of the Cambridge Philosophical Society , 70 (2): 211–218, Бибкод : 1971PCPS...70..211F , doi : 10.1017/ S0305004100049811 , МР 0289365 , S2CID 122686848 .
Кантор, Зелигманн (1882), «О конфигурациях (3, 3) с индексами 8, 9 и их связи с кривыми третьего порядка», труды Класса математических и естественных наук Императорской Академии наук, Вена , 84 (1): 915–932 .
Лийнен, Эрвин; Сеулеманс, Арноут (2004), «Ориентированные двухклеточные вложения графа и их классификация симметрии: алгоритмы генерации и тематическое исследование графа Мёбиуса-Кантора», Журнал химической информации и моделирования , 44 (5): 1552–1564, doi : 10.1021/ci049865c , PMID 15446812 .
Марушич, Драган ; Писански, Томаж (2000), «Замечательный обобщенный граф Петерсена G (8,3)» , Mathematica Slovaca , 50 : 117–121 .
МакМаллен, Питер (1992), «Правильные многогранники типа $\{p,3\}$ с $2p$ вершины», Dedicated Geometry , 43 (3): 285–289, doi : 10.1007/BF00151518 , S2CID 119591683 .
Маккуиллан, Дэн; Рихтер, Р. Брюс (1992), «О числах пересечений некоторых обобщенных графов Петерсена», Discrete Mathematics , 104 (3): 311–320, doi : 10.1016/0012-365X(92)90453-M , MR 1171327 .
Мёбиус, Август Фердинанд (1828 г.): «Можно ли каждую из двух трёхгранных пирамид назвать переписанной и вписанной относительно другой одновременно?» , Журнал чистой и прикладной математики , 3 : 273–278 ; в Собрании сочинений (1886), т. 1, стр. 439–446.
Такер, Томас В. (1984), «Существует только одна группа второго рода», Журнал комбинаторной теории, серия B , 36 (3): 269–275, doi : 10.1016/0095-8956(84)90032-7 .
Трелфолл, Уильям (1932), «Групповые картинки», Трактаты математическо-физического класса Саксонской академии наук , 41 (6): 1–59 .

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

[FOOTNOTECoxeter1950-1] Перейти обратно: ^а ^б Коксетер 1950 .

[2] OEIS A110507 Последовательность

[FOOTNOTEMcQuillanRichter1992-3] Маккуиллан и Рихтер 1992 .

[FOOTNOTEMarušičPisanski2000-4] Перейти обратно: ^а ^б ^с Марушич и Писански 2000 .

[5] Коксетер (1950) приписывает это встраивание Трелфоллу (1932) .

[FOOTNOTEConderDobcsányi2002-6] Кондер и Добчани 2002 .

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

[FOOTNOTEMcMullen1992-8] Макмаллен 1992 .

[9] Брауэр, Эндрю Э. «График Мёбиуса-Кантора» . www.win.tue.nl. Проверено 21 июля 2024 г.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]