TOPICS
Search

Goddard-Henning Graph


Goddard-HenningGraph

The Goddard-Henning graph, illustrated above in several embeddings, is the 9-node planar graph of graph diameter 2 having domination number gamma=3. It was first constructed by MacGillivray and Seyffarth (1996) and subsequently proved (Goddard and Henning 2002, Henning and Yeo 2013, pp. 55-56) to be the unique diameter-2 planar graph with gamma=3; all other diameter-2 planar graphs have domination number at most 2.

It is the skeleton of the Goddard-Henning enneahedron.

The Goddard-Henning graph can be obtained from the generalized quadrangle GQ(2,1) by deleting two edges and hence is a unit-distance graph.

It is also self-dual.


See also

Domination Number, Goddard-Henning Enneahedron

Explore with Wolfram|Alpha

References

Goddard, W. Henning, M. A. "Domination in Planar Graphs with Small Diameter." J. Graph Th. 40, 1-25, 2002.Henning, M. A. and Yeo, A. Total Domination in Graphs. New York: Springer, pp. 55-56, 2013.MacGillivray, G. and Seyffarth, K. "Domination Numbers of Planar Graphs." J. Graph Th. 22, 213-219, 1996.

Cite this as:

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

Subject classifications