TOPICS
Search

Subhamiltonian Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

A subhamiltonian graph is a graph that can be extended by adding edges inside faces of a planar embedding to a planar Hamiltonian graph. Since the augmented graph is required to be planar, the original subhamiltonian graph must necessarily be planar.

Every planar graph with maximum vertex degree Delta>=4 is subhamiltonian (Bekos et al. 2014). More generally, every polyhedral graph is subhamiltonian (although not necessarily Hamiltonian), a result which follows from classical results on planar embeddings due to Barnette and Grünbaum (1969).

Classes for which all members are planar and Hamiltonian are subhamiltonian, including 4-connected planar graphs (Nishizeki and Chiba 2008), Halin graphs (Cornuéjols et al. 1983), and triangular grid graphs. Series-parallel graphs and outerplanar graphs (including trees) are also subhamiltonian.

A subhamiltonian graph has book thickness at most 2, and a subhamiltonian graph that is not outerplanar has book thickness exactly 2.

See also

Almost Hamiltonian Graph, Book Thickness, Hamiltonian Graph, Hypohamiltonian Graph, Perfectly Hamiltonian Graph, Perihamiltonian Graph

Explore with Wolfram|Alpha

References

Barnette, D. W. and Grünbaum, B. "On Steinitz's Theorem concerning Convex 3-Polytopes and on Some Properties of Planar Graphs." In The Many Facets of Graph Theory (Ed. G. Chartrand and S. F, Kapoor). Berlin: Springer-Verlag, pp. 27-40, 1969.Bekos, M. A.; Gronemann, M.; and Raftopoulou, C. N. "Two-Page Book Embeddings of 4-Planar Graphs." STACS 2014. https://arxiv.org/abs/1401.0684.Bernhart, F. R.; Kainen, P. C. "The Book Thickness of a Graph." J. Combin. Th., Ser. B 27, 320-331, 1979.Cornuéjols, G.; Naddef, D.; and Pulleyblank, W. R. "Halin Graphs and the Travelling Salesman Problem." Math. Programming 26, 287-294, 1983.Di Giacomo, E. and Liotta, G. "The Hamiltonian Augmentation Problem and Its Applications to Graph Drawing." In WALCOM: Algorithms and Computation, 4th International Workshop, WALCOM 2010, Dhaka, Bangladesh, February 10-12, 2010. Berlin: Springer, pp. 35-46, 2010.Heath, L. S. "Embedding Outerplanar Graphs in Small Books." SIAM J. Alg. Disc. Meth. 8, 198-218, 1987.Nishizeki, T. and Chiba, N. "Hamiltonian Cycles." Ch. 10 in Planar Graphs: Theory and Algorithms. New York: Dover, pp. 171-184, 2008.

Cite this as:

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

Subject classifications