TOPICS
Search

Uniquely Pancyclic Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

A uniquely pancyclic graph is a graph that has exactly one cycle of each length between 3 and the graph's vertex count. Uniquely pancyclic graphs are therefore a special case of pancyclic graphs.

By their definition, uniquely pancyclic graphs are also uniquely Hamiltonian.

UniquelyPancyclicGraph

Determining which simple graphs are uniquely pancyclic is an open problem attributed to Roger Entringer and posed by Bondy and Murty (1976, Problem 10, p. 247). It is conjectured that the 7 graphs illustrated above (Shi 1986) are the only uniquely pancyclic graphs, but proof or discovery of additional examples have thus far remained elusive.

See also

Graph Cycle, Pancyclic Graph, Uniquely Hamiltonian Graph

Explore with Wolfram|Alpha

References

Bondy, J. A. and Murty, U. S. R. Problem 10 in "Appendix IV: Unsolved Problems." Graph Theory with Applications. New York: North Holland, pp. 246-253, 1976.Exoo, G. "Uniquely Pancyclic Graphs." https://isu.indstate.edu/~gexoo/Graphs/PANCYCLIC/.George, J. C.; Khodkar, A.; and Wallis, W. D. "Uniquely Pancyclic Graphs." Ch. 5 in Pancyclic and Bipancyclic Graphs. Cham, Switzerland: Springer, pp. 49-67, 2016.House of Graphs. Uniquely Pancyclic Graphs. Triangle K3 and House Graph (Theta(1,2,3)).Locke, S. C. "Uniquely Pancyclic Graphs." http://math.fau.edu/locke/UPCGraph.htm.Markström, K. "A Note on Uniquely Pancyclic Graphs." Australasian J. Combin. 44, 105-110, 2009.Shi, Y. "Some Theorems of Uniquely Pancyclic Graphs." Disc. Math. 59, 167-180, 1986.Shi, Y. B.; Yap, H. P.; and Teo, S. K. "On Uniquely r-Pancyclic Graphs." Ann. New York Acad. Sci. 576, 487-499, 1989.

Referenced on Wolfram|Alpha

Uniquely Pancyclic Graph

Cite this as:

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

Subject classifications