TOPICS

# Icosahedral Graph

The icosahedral graph is the Platonic graph whose nodes have the connectivity of the regular icosahedron, as well as the great dodecahedron, great icosahedron Jessen's orthogonal icosahedron, and small stellated dodecahedron. The icosahedral graph has 12 vertices and 30 edges and is illustrated above in a number of embeddings.

Since the icosahedral graph is regular and Hamiltonian, it has a generalized LCF notation. In fact, there are two distinct generalized LCF notations of order 6-- and --8 of order 2, and 17 of order 1, illustrated above.

It is implemented in the Wolfram Language as GraphData["IcosahedralGraph"].

It is a distance-regular graph with intersection array , and therefore also a Taylor graph. It is also distance-transitive.

The icosahedral graph is graceful (Gardner 1983, pp. 158 and 163-164; Gallian 2018, p. 35), as shown by the labeling above which gives absolute differences of adjacent labeled vertices consisting of precisely the numbers 0-30 inclusive. There are 24 fundamentally different graceful labelings (i.e., graceful labelings that are distinct modulo subtractive complementation and the symmetries of the graph), giving a total of 5760 graceful labelings in all (Bert Dobbelaere, pers. comm., Oct. 2, 2020). The computation by Ashkok Kumar Chandra that found 5 fundamentally different solutions, as reported by Gardner (1983, pp. 163-164), therefore seems to be in error.

There are two minimal integral embeddings of the icosahedral graph, illustrated above, all with maximum edge length of 8 (Harborth and Möller 1994).

The minimal planar integral embedding of the icosahedral graph has maximum edge length of 159 (Harborth et al. 1987).

The skeletons of the great dodecahedron, great icosahedron, and small stellated dodecahedron are all isomorphic to the icosahedral graph.

Removing any edge from the icosahedral graph gives the Tilley graph.

The chromatic polynomial of the icosahedral graph is

and the chromatic number is 4.

Its graph spectrum is (Buekenhout and Parker 1998; Cvetkovic et al. 1998, p. 310). Its automorphism group is of order (Buekenhout and Parker 1998).

The plots above show the adjacency, incidence, and graph distance matrices for the icosahedral graph.

The adjacency matrix for the icosahedral graph with appended, where is a unit matrix and is an identity matrix, is a generator for the Golay code.

The following table summarizes properties of the icosahedral graph.

 property value automorphism group order 120 characteristic polynomial chromatic number 4 claw-free yes clique number 3 determined by spectrum ? diameter 3 distance-regular graph yes dual graph name dodecahedral graph edge chromatic number 5 edge connectivity 5 edge count 30 Eulerian no girth 3 Hamiltonian yes Hamiltonian cycle count 2560 Hamiltonian path count ? integral graph no independence number 3 line graph no perfect matching graph no planar yes polyhedral graph yes polyhedron embedding names great dodecahedron, great icosahedron, icosahedron, Jessen's orthogonal icosahedron, small stellated dodecahedron radius 3 regular yes spectrum square-free no traceable yes triangle-free no vertex connectivity 5 vertex count 12 weakly regular parameters

Cubical Graph, Dodecahedral Graph, Octahedral Graph, Platonic Graph, Tetrahedral Graph, Tilley Graph

## Explore with Wolfram|Alpha

More things to try:

## References

Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 234, 1976.Buekenhout, F. and Parker, M. "The Number of Nets of the Regular Convex Polytopes in Dimension ." Disc. Math. 186, 69-94, 1998.Cvetković, D. M.; Doob, M.; and Sachs, H. Spectra of Graphs: Theory and Applications, 3rd rev. enl. ed. New York: Wiley, 1998.DistanceRegular.org. "Icosahedron." http://www.distanceregular.org/graphs/icosahedron.html.Gallian, J. "Dynamic Survey of Graph Labeling." Elec. J. Combin. DS6. Dec. 21, 2018. https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6.Gardner, M. "Golomb's Graceful Graphs." Ch. 15 in Wheels, Life, and Other Mathematical Amusements. New York: W. H. Freeman, pp. 152-165, 1983.Godsil, C. and Royle, G. Algebraic Graph Theory. New York: Springer-Verlag, p. 127, 2001.Harborth, H. and Möller, M. "Minimum Integral Drawings of the Platonic Graphs." Math. Mag. 67, 355-358, 1994.Harborth, H.; Kemnitz, A.; Möller, M.; and Süssenbach, A. "Ganzzahlige planare Darstellungen der platonischen Körper." Elem. Math. 42, 118-122, 1987.Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, p. 266, 1998.

## Cite this as:

Weisstein, Eric W. "Icosahedral Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/IcosahedralGraph.html