Граф Дезарга

Граф Дезарга
Названо на честь	Жерара Дезарга
Вершин	20
Ребер	30
Радіус	5
Діаметр	5
Обхват	6
Автоморфізм	240 (S5× Z/2Z)
Хроматичне число	2
Хроматичний індекс	3
Число черг	2
Властивості	Кубічний Дистанційно-регулярний Гамільтонів Двочастковий Симетричний

Граф Дезарга у теорії графів — це дистанційно-транзитивний кубічний граф з 20 вершинами та 30 ребрами.[1] Названий на честь Жерара Дезарга. Граф виникає з декількох різних комбінаторних конструкцій, має високий рівень симетрії, є єдиним відомим непланарним частковим кубом, а також доданий до хімічних баз даних.

Назва «Граф Дезарга» також використовується для опису десяти-вершинного графу, додатку до графу Петерсона, що також може бути сформованим як двостороння половина^[en] 20 вершинного графу Дезарга.[2]

Конструкція

Існує декілька різних варіантів побудови графу Дезарга:

• Він є узагальненим графом Петерсена G(10, 3). Щоб сформувати Граф Дезарга цим шляхом, об'єднайте десять вершин у звичайний десятикутник та з'єднайте інші десять вершин у десяти-кінцеву зірку, що з'єднує пари вершин на відстані три у другому десятикутнику. Граф Дезарга складається з 20 сторін цих двох полігонів разом з додатковими 10 сторонами, об'єднуючи точки одного десятикутника з відповідними точками іншого.
• Також, це граф Леві з Конфігурація Дезарга|конфігурації Дезарга. Ця конфігурація складається з 10 точок та 10 ліній, що описують два трикутники у перспективі, їх центр перспективи та їх вісь перспективи. Граф Дезарга має по одній вершині на кожну точку, по одній вершині на кожну лінію, на кожну випадкову точку перетину ліній. Теорема Дезарга, названа на честь французького математика 17 століття Жерара Дезарга, описує деяку кількість точок та ліній, що утворюють цю конфігурацію, і конфігурація разом із графом беруть назву також від нього.
• Це двочасткове подвійне покриття^[en] графу Петерсена, сформоване заміною кожної вершини з графу парою вершин і кожної з сторін графу парою перехресних сторін.
• Це двосторонній граф Кнезера H_5,2. Його вершини можуть бути відмічені 10 підмножинами з двох елементів та 10 підмножинами з трьох елементів п'яти-елементної множини, зі стороною, що з'єднує дві вершини, коли одна з відповідних множин є підмножиною іншої. Так само, Граф Дезарга — це індукований підграф 5-вимірного гіперкуба, визначений вершинами по 2 та по 3.
• Граф Дезарга це Гамільтонів граф і може бути побудований з LCF-нотації: [5,−5,9,−9]^5. Як припустив Ердеш, для позитивного k, підграф 2k+1-вимірного гіперкуба індукований вершинами по k та k+1 є гамільтоновим графом. Гамільтоновість графу Дезарга не є несподіванкою. Також з сильнішої кон'юнктури Ловаса, окрім декількох відомих контра-прикладів, випливає, що усі транзитивні по вершинам графи мають цикли Гамільтона.

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

Граф Дезарга — це симетричний граф: так кожна вершина симетрична будь-якій іншій вершині, сторона — будь-якій іншій стороні. Його група симетрії має порядок 240 і ізоморфна добутку симетричної групи на 5 пунктів з групою порядку 2.

Можна інтерпретувати це подання продукту групи симетрії у вираженні конструкцій графу Дезарга: симетрична група з п'яти точок — це симетрична група конфігурації Дезарга, і підгрупа другого порядку змінює місцями ролі вершин, що представляють точки конфігурації Дезарга і вершин, які представляють лінії. Крім того, з точки зору двостороннього графу Кнезера, симетрична група з п'яти точок діє окремо на двох-елементні та три-елементні підмножини з п'яти точок, і доповнення підмножин утворює групу другого порядку, що перетворює один вид підмножини в інший. Симетрична група з п'яти точок також є групою симетрії графу Петерсена, і підгрупа другого порядку міняє місцями вершини з кожної пари вершин, утворених у конструкції подвійного накриття.

Узагальнений граф Петерсена g(n, k) є транзитивним по вершинах тоді і тільки тоді, коли k = 2 або k2 ≡ ±1 (mod n) і транзитивний по сторонах тільки у наступних семи випадках: (n, k) = (4, 1), (5, 2), (8, 3), (10, 2), (10, 3), (12, 5), (24, 5).[3] Отже, Граф Дезарга є лише одним з семи узагальнених симетричних графів Петерсона. Серед цих семи графів є кубічний граф G(4, 1), граф Петерсена G(5, 2), граф Мебіуса — Кантора G(8, 3), граф-додекаедр G(10, 2)та граф Науру G(12, 5).

Характеристичний поліном графу Дезарга

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

Тому граф Дезарга — це цілий граф: його спектр складається лише з цілих чисел.

Застосування

У хімії граф Дезарга відомий як граф Дезарга — Леві, він використовується для організації систем стереоізомерів 5-лігандних з'єднань. У цьому застосуванні 30 сторін графу відповідають псевдообертанню ліганд.[4][5]

Інші властивості

Граф Дезарга має 6 прямолінійних перетинів і є найменшим кубічним графом з такою кількістю перетинів (послідовність A110507 з Онлайн енциклопедії послідовностей цілих чисел, OEIS). Це єдиний відомий неплоский частково кубічний граф.[6]

Граф Дезарга має хроматичне число 2 , хроматичний індекс 3 , радіус 5, діаметр 5 і обхват 6. Також він є 3-вершинно-зв'язним та 3-реберно-зв'язним графом Гамільтона.

Усі кубічні дистанційно-регулярні графи відомі.[7] Граф Дезарга — 1 з 13 таких графів.

Граф Дезарга може бути вбудований як самостійна подвійна мапа Петрі у неорієнтованому многовиді шостого роду з декагональними зовнішніми сторонами.

Галерея

• 
  Граф Дезарга розфарбований щоб виділити різні цикли.
• 
  Хроматичний індекс графу Дезарга - 3.
• 
  Хроматичне число графу Дезарга - 2.

Див. також

• Конфігурація Дезарга

Примітки

1. Weisstein, Eric W. Desargues Graph(англ.) на сайті Wolfram MathWorld.
2. Kagno, I. N. (1947), Desargues' and Pappus' graphs and their groups, American Journal of Mathematics, The Johns Hopkins University Press, 69 (4): 859—863, doi:10.2307/2371806, JSTOR 2371806.
3. Frucht, R.; Graver, J. E.; Watkins, M. E. (1971), The groups of the generalized Petersen graphs, Proceedings of the Cambridge Philosophical Society, 70 (02): 211—218, doi:10.1017/S0305004100049811.
4. Balaban, A. T.; Fǎrcaşiu, D.; Bǎnicǎ, R. (1966), Graphs of multiple 1, 2-shifts in carbonium ions and related systems, Rev. Roum. Chim., 11: 1205
5. Mislow, Kurt (1970), Role of pseudorotation in the stereochemistry of nucleophilic displacement reactions, Acc. Chem. Res., 3 (10): 321—331, doi:10.1021/ar50034a001
6. Klavžar, Sandi; Lipovec, Alenka (2003), Partial cubes as subdivision graphs and as generalized Petersen graphs, Discrete Mathematics, 263: 157—165, doi:10.1016/S0012-365X(02)00575-7
7. Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, 1989.