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
erefbarbell 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

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.