Jump to content

Dürer graph

From Wikipedia, the free encyclopedia
Melencolia I by Albrecht Dürer, the first appearance of Dürer's solid (1514).

In the mathematical field of graph theory, the Dürer graph is an undirected graph with 12 vertices and 18 edges. It is named after Albrecht Dürer, whose 1514 engraving Melencolia I includes a depiction of Dürer's solid, a convex polyhedron having the Dürer graph as its skeleton. Dürer's solid is one of only four well-covered simple convex polyhedra.

Dürer's solid

[edit]

Dürer's solid is combinatorially equivalent to a cube with two opposite vertices truncated,[1] although Dürer's depiction of it is not in this form but rather as a truncated rhombohedron or truncated triangular trapezohedron.[2] The exact geometry of the solid depicted by Dürer is a subject of some academic debate, with different hypothetical values for its acute angles ranging from 72° to 82°.[3]

Graph-theoretic properties

[edit]
Dürer graph
The Dürer graph
Named afterAlbrecht Dürer
Vertices12
Edges18
Radius3
Diameter4
Girth3
Automorphisms12 (D6)
Chromatic number3
Chromatic index3
PropertiesCubic
Planar
Well-covered
Table of graphs and parameters

The Dürer graph is the graph formed by the vertices and edges of the Dürer solid. It is a cubic graph of girth 3 and diameter 4. As well as its construction as the skeleton of Dürer's solid, it can be obtained by applying a Y-Δ transform to the opposite vertices of a cube graph, or as the generalized Petersen graph G(6,2).[4] As with any graph of a convex polyhedron, the Dürer graph is a 3-vertex-connected simple planar graph.

The Dürer graph is a well-covered graph, meaning that all of its maximal independent sets have the same number of vertices, four. It is one of four well-covered cubic polyhedral graphs and one of seven well-covered 3-connected cubic graphs. The only other three well-covered simple convex polyhedra are the tetrahedron, triangular prism, and pentagonal prism.[5]

The Dürer graph is Hamiltonian, with LCF notation [-4,5,2,-4,-2,5;-].[6] More precisely, it has exactly six Hamiltonian cycles, each pair of which may be mapped into each other by a symmetry of the graph.[7]

Symmetries

[edit]

The automorphism group both of the Dürer graph and of the Dürer solid (in either the truncated cube form or the form shown by Dürer) is isomorphic to the dihedral group of order 12, denoted D6.

[edit]

Notes

[edit]
  1. ^ Weisstein, Eric W., "Dürer's Solid", MathWorld
  2. ^ Weber (1900).
  3. ^ Weitzel (2004).
  4. ^ Pisanski & Tucker (2002).
  5. ^ Campbell & Plummer (1988); Campbell, Ellingham & Royle (1993).
  6. ^ Castagna & Prins (1972) attribute the proof of Hamiltonicity of a class of generalized Petersen graphs that includes the Dürer graph to a 1968 Ph.D. thesis of G. N. Robertson at the University of Waterloo.
  7. ^ Schwenk (1989).

References

[edit]