The dodecahedral graph is the Platonic graph corresponding to the connectivity of the vertices of a dodecahedron, illustrated above in four embeddings. The left embedding shows a stereographic projection of the dodecahedron, the second an orthographic projection, the third is from Read and Wilson (1998, p. 162), and the fourth is derived from LCF notation.
It is the cubic symmetric denoted and is isomorphic to the generalized Petersen graph . It can be described in LCF notation as [10, 7, 4, , , 10, , 7, , .
It is distance-regular with intersection array and is also distance-transitive.
It is also a unit-distance graph (Gerbracht2008), as shown above in a unit-distance drawing.
Finding a Hamiltonian cycle on this graph is known as the icosian game. The dodecahedral graph is not Hamilton-connected and is the only known example of a vertex-transitive Hamiltonian graph (other than cycle graphs ) that is not H-*-connected (Stan Wagon, pers. comm., May 20, 2013).
The minimal planar integral drawing of the dodecahedral graph has maximum edge length of 2 (Harborth et al. 1987). It is also graceful (Gardner 1983, pp. 158 and 163-164; Gallian 2018, p. 35) with many fundamentally different labelings (Gardner 1983, p. 164).
The dodecahedral graph is implemented in the WolframLanguage as GraphData["DodecahedralGraph"].
It can be constructed as the graph expansion of with steps 1 and 2, where is a path graph (Biggs 1993, p. 119).
The skeleton of the great stellated dodecahedronis isomorphic to the dodecahedral graph.
The line graph of the dodecahedral graph is the icosidodecahedral graph.
The dodecahedral graph has 20 nodes, 30 edges, vertex connectivity 3, edge connectivity 3, graph diameter 5, graph radius 5, and girth 5. Its has chromatic number 3. Its graph spectrum is (Buekenhout and Parker 1998; Cvetkovic et al. 1998, p. 308). Its automorphism group is of order (Buekenhout and Parker 1998).
The dodecahedral graph has chromatic polynomial
The plots above show the adjacency, incidence, and graph distance matrices for the dodecahedral graph.
The bipartite double graph of the dodecahedral graph is the cubic symmetric graph .
The following table summarizes properties of the dodecahedral graph.
|automorphism group order||120|
|determined by spectrum||yes|
|dual graph name||icosahedral graph|
|edge chromatic number||3|
|generalized Petersen indices|
|Hamiltonian cycle count||60|
|Hamiltonian path count||?|
|line graph name||icosidodecahedral graph|
|perfect matching graph||no|
|polyhedron embedding names||dodecahedron, great stellated dodecahedron|
|weakly regular parameters|