Граф Дюрера

«Меланхолія» Альбрехта Дюрера

Граф Дюрера — неорієнтований кубічний граф з 12 вершинами і 18 ребрами. Граф названо ім'ям Альбрехта Дюрера, чия гравюра «Меланхолія» (1514) містила зображення так званого багатогранника Дюрера — опуклого багатогранника, кістяком якого є граф Дюрера. Багатогранник Дюрера є одним з чотирьох можливих добре покритих простих опуклих багатогранників.

Багатогранник Дюрера

Багатогранник Дюрера комбінаторно еквівалентний кубу з двома зрізаними протилежними вершинами, хоча на малюнку Дюрера він, швидше, зображений як зрізаний ромбоедр або тригранний зрізаний трапецоїд. Точні геометричні властивості намальованого Дюрером багатогранника є предметом академічних суперечок, у яких припускаються різні гіпотетичні значення (гострих) кутів від 72° до 82°.

Властивості графу

Граф Дюрера — це граф, утворений вершинами і ребрами багатогранника Дюрера. Граф є кубічним з обхватом 3 і діаметром 4. Оскільки граф є кістяком багатогранника Дюрера, його можна отримати, застосувавши перетворення трикутник-зірка протилежних вершин графу куба, або як узагальнений граф Петерсена $G(6,2)$. Як і будь-який інший граф опуклого багатогранника, граф Дюрера є вершинно 3-зв'язним простим планарним графом.

Граф Дюрера є добре покритим, що означає, що всі його найбільші незалежні множини мають однакове число вершин — чотири. Граф є одним з добре покритих кубічних багатогранних графів і одним з семи добре покритих 3-зв'язних кубічних графів. Іншими трьома добре покритими простими опуклими багатогранниками є тетраедр, трикутна призма і п'ятикутна призма.

Граф Дюрера є гамільтоновим з LCF-позначенням [-4,5,2,-4,-2,5;-]. Точніше, граф має рівно шість гамільтонових циклів, кожну пару яких можна відобразити в будь-яку іншу симетріями графу.

Симетрії

Група автоморфізмів як графу Дюрера, так і багатогранника Дюрера (у вигляді зрізаного куба або у формі, наведеній Дюрером) ізоморфна діедральній групі $D_{6}$ порядку 12.

Галерея

• 
  Хроматичний індекс графу Дюрера дорівнює 3.
• 
  Хроматичне число графу Дюрера дорівнює 3.
• 
  Граф Дюрера гамільтонів.

Література

• S. R. Campbell, M. N. Ellingham, Gordon F. Royle. A characterisation of well-covered cubic graphs // Journal of Combinatorial Mathematics and Combinatorial Computing. — 1993. — Т. 13 (4 червня). — С. 193–212.
• Stephen R. Campbell, Michael D. Plummer. On well-covered 3-polytopes // Ars Combinatoria. — 1988. — Т. 25, вип. A (4 червня). — С. 215–242.
• Frank Castagna, Geert Prins. Every Generalized Petersen Graph has a Tait Coloring // Pacific Journal of Mathematics. — 1972. — Т. 40 (4 червня). — DOI:10.2140/pjm.1972.40.53.
• Allen J. Schwenk. Enumeration of Hamiltonian cycles in certain generalized Petersen graphs // Journal of Combinatorial Theory. — 1989. — Т. 47, вип. 1 (4 червня). — С. 53–59. — (Series B). — DOI:10.1016/0095-8956(89)90064-6.
• P. Weber. Beiträge zu Dürers Weltanschauung—Eine Studie über die drei Stiche Ritter, Tod und Teufel, Melancholie und Hieronymus im Gehäus. — Strassburg, 1900. — 4 червня. (як процитовано у Вайцеля ().
• Hans Weitzel. A further hypothesis on the polyhedron of A. Dürer's engraving Melencolia I // Historia Mathematica. — 2004. — Т. 31, вип. 1 (4 червня). — С. 11–14. — DOI:10.1016/S0315-0860(03)00029-6.