TOPICS

Graph Circumference

The circumference of a graph is the length of any longest cycle in a graph. Hamiltonian graphs on vertices therefore have circumference of .

For a cyclic graph, the maximum element of the detour matrix over all adjacent vertices is one smaller than the circumference.

The graph circumference of a self-complementary graph is either (i.e., the graph is Hamiltonian), , or (Furrigia 1999, p. 51).

Circumferences of graphs for various classes of nonhamiltonian graphs are summarized in the table below.

Almost Hamiltonian Graph, Detour Matrix, Girth, Graph Cycle, Graph Diameter, Graph Eccentricity, Graph Radius, Hamiltonian Number, Longest Path

Explore with Wolfram|Alpha

More things to try:

References

Farrugia, A. "Self-Complementary Graphs and Generalisations: a Comprehensive Reference Manual." Aug. 1999. http://www.alastairfarrugia.net/sc-graph/sc-graph-survey.pdf.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, p. 13, 1994.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 192, 1990.Zamfirescu, T. "On Longest Paths and Circuits in Graphs." Math. Scand. 38, 211-239, 1976.

Referenced on Wolfram|Alpha

Graph Circumference

Cite this as:

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