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.