Graph Circumference

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

For a cyclic graph, the maximum element a_(ij) of the detour matrix over all adjacent vertices (i,j) is one smaller than the circumference.

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

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

See also

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

Explore with Wolfram|Alpha


Farrugia, A. "Self-Complementary Graphs and Generalisations: a Comprehensive Reference Manual." Aug. 1999., 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.

Subject classifications