 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.

 class circumference barbell graph  -bishop graph book graph 6 complete bipartite graph for   -cone graph gear graph grid graph  grid graph  helm graph  -knight graph pan graph sunlet graph  web graph wheel graph   -windmill graph 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