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.
-
for 
-
-
-
