Граф Мебіуса – Кантора

У теорії графів гра́фом Ме́біуса — Ка́нтора називається симетричний двочастковий кубічний граф з 16 вершинами і 24 ребрами, названий на честь Августа Фердинанда Мебіуса і Зелігмана Кантора (1857—1903). Його можна визначити як узагальнений граф Петерсена G(8,3). Тобто, він утворений вершинами восьмикутника, з'єднаними з восьмикутною зіркою, в якій кожна точка з'єднана з третьої за рахунком точкою.

Граф Мебіуса — Кантора
Названо на честь	Август Фердинанд Мебіус і Зелігман Кантор
Вершин	16
Ребер	24
Радіус	4
Діаметр	4
Обхват	6
Автоморфізм	96
Хроматичне число	2
Хроматичний індекс	3
Рід	1
(Число черг)	2
Властивості	Симетричний Гамільтонів Двочастковий Кубічний Граф одиничних відстаней Граф Келі Досконалий

Конфігурація Мебіуса — Кантора

Докладніше: (Конфігурація Мебіуса — Кантора)

(Конфігурація Мебіуса — Кантора)

Мебіус (Möbius 1828) поставив запитання, чи існує пара багатокутників з p сторонами в кожному, які володіють властивістю, що вершини одного багатокутника лежать на прямих, що проходять через сторони іншого, і навпаки. Якщо так, вершини і сторони цих багатокутників повинні утворювати (проєктивну конфігурацію). Для p = 4 не існує рішення на евклідовій площині, але Кантор знайшов пару багатокутників такого типу в узагальненні завдання, в якому точки і ребра належать Комплексній проективній площині. Тобто, у рішенні Кантора координатами вершин багатокутника є комплексні числа. Рішення Кантора для p = 4 — пара взаємно вписаних чотирикутника на комплексній проективної площини, називається конфігура́цією Ме́біуса — Ка́нтора. Граф Мебіуса — Кантора отримав своє ім'я від конфігурації Мебіуса — Кантора, оскільки він є графом Леві цій конфігурації. Граф має одну вершину для кожної точки конфігурації і по точці для кожної трійки, а ребра з'єднують дві вершини, якщо одна вершина відповідає точці, а інша трійці, що містить цю точку.

Зв'язок з гіперкубом

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

Топологія

Узагальнений граф Мебіуса — Кантора, вкладений в тор. Ребра, що виходять вгору з центрального квадрата слід розглядати з'єднаними з відповідними ребрами, що виходять з квадрата вниз, а виходять з квадрата ребра зліва слід розглядати з'єднаними з відповідними ребрами, що виходять з квадрата вправо.

Граф Мебіуса — Кантора не можна вкласти в площину без перетинів, його число схрещень дорівнює 4, і він є найменшим кубічним графом з таким числом схрещень (послідовність A110507 в (OEIS)). Крім того, граф дає приклад графу, усі підграфи якого мають кількість перетинів на два і більше від кількості перетинів самого графу. Однак він є (тороїдальним) — існує його вкладення в тор, при якому всі його грані є шестикутниками. Двоїстий граф цього вкладення — це (граф гіпероктаедра) K_2,2,2,2.

Існує навіть більш симетричне вкладення графу Мебіуса — Кантора в ^[en], що є регулярним відображенням і має шестеро восьмикутних граней, в якому всі 96 симетрій графу можна здійснити як симетрії вкладення. Коксетер приписує це вкладення Трелфалу. 96-елемантну групу симетрії вкладення має граф Келі, який може бути вкладений в подвійній тор. Такер показав, що це єдина група роду два. Скульптура Де Вітта Годфрея (DeWitt Godfrey) і Дуейн Мартинця (Duane Martinez) у вигляді подвійного тора з вкладеним графом Мебіуса — Кантора була представлена ​​в Технічному музеї Словенії на шостій Словенської Міжнародній конференції з теорії графів в 2007. У 2013 обертаюча версія скульптури була представлена ​​в Колгейтском університеті.

Граф Мебіуса — Кантора допускає вкладення в ^[en] (тор третього роду), яке дає ^[en], що має чотири 12-кутні грані.

Лижнен і Кулеманс, досліджуючи можливі хімічні вуглецеві структури, вивчили родину усіх вкладень графу Мебіуса — Кантора в двовимірні многовиди. Вони показали, що існує 759 нееквівалентних вкладень.

Алгебраїчні властивості

• Група автоморфізмів графу Мебіуса — Кантора — це група порядку 96. Вона діє транзитивно на вершини та на ребра, тому Граф Мебіуса — Кантора є симетричним.
• У нього є автоморфізми, які переводять будь-яку вершину в будь-яку іншу і будь-яке ребро в будь-яке інше.
• Згідно зі списком Фостера граф Мебіуса — Кантора є єдиним симетричним графом з 16 вершинами і найменшим кубічним симетричним графом, який не є дистанційно-транзитивним.
• Граф Мебіуса — Кантора є графом Келі.

Узагальнений граф Петерсена 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) (Frucht, Graver, Watkins, 1971). Таким чином, граф Мебіуса — Кантора є одним з цих семи. Його симетричне вкладення в подвійній тор — одна з семи правильних кубічних карт, для яких загальне число вершин вдвічі більше числа вершин граней. Серед семи симетричних узагальнених графів Петерсена знаходиться кубічний граф G (4,1), граф Петерсена G (5,2), граф додекаедра G (10,2), граф Дезарга G (10,3) і граф Науру G (12,5).

Характерний многочлен графу Мебіуса — Кантора дорівнює

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

Примітки

1. Coxeter, 1950
2. Dan McQuillan, R. Bruce Richter On the crossing numbers of certain generalized Petersen graphs // Discrete Mathematics. — 1992. — Т. 104, вып. 3. — С. 311—320.
3. Coxeter, 1950.
4. Threlfall, 1932.
5. Tucker, 1984.
6. Marušič, Pisanski, 2000
7. Lijnen та Ceulemans, 2004.
8. Royle, G. F016A data
9. Conder, M.[en], Dobcsányi, P. «Trivalent Symmetric Graphs Up to 768 Vertices.» J. Combin. Math. Combin. Comput. 40, 41-63, 2002.
10. McMullen, 1992

Джерела

• Coxeter, H. S. M. (1950), Self-dual configurations and regular graphs, (Bulletin of the American Mathematical Society), 56 (5): 413—455, doi:10.1090/S0002-9904-1950-09407-5 (англ.)
• Lijnen, E.; Ceulemans, A. (2004), 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., 44 (5): 1552—1564, doi:10.1021/ci049865c, PMID 15446812 (англ.)
• (1984), There is only one group of genus two, Journal of Combinatorial Theory, Series B, 36 (3): 269—275, doi:10.1016/0095-8956(84)90032-7 (англ.)
• Threlfall, W. (1932), Gruppenbilder, Abhandlungen der Mathematisch-Physischen Klasse der Sächsischen Akademie der Wissenschaften, 41 (6): 1—59 (нім.)

Посилання

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