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.

classcircumference
erefbarbell graphn
(n,n)-bishop graph{n^2/2   for n even; (n^2+1)/2   for n odd
book graph S_(n+1) square P_26
complete bipartite graph K_(m,n) for min(m,n)>12min(m,n)
(m,n)-cone graph{2m   for m<=n; m+n   otherwise
gear graph2n
grid graph P_m square P_n{mn-1   for m,n odd; mn   otherwise
grid graph P_l square P_m square P_n{lmn-1   for l,m,n odd; lmn   otherwise
helm graphn+1
(n,n)-knight graph{14   for n=4; n^2   for even n>4; n^2-1   for odd n>2
pan graphn
sunlet graph C_n circledot K_1n
web graph2n
wheel graph W_nn
(m,n)-windmill graphn

Wolfram Web Resources

Mathematica »

The #1 tool for creating Demonstrations and anything technical.

Wolfram|Alpha »

Explore anything with the first computational knowledge engine.

Wolfram Demonstrations Project »

Explore thousands of free applications across science, mathematics, engineering, technology, business, art, finance, social sciences, and more.

Computerbasedmath.org »

Join the initiative for modernizing math education.

Online Integral Calculator »

Solve integrals with Wolfram|Alpha.

Step-by-step Solutions »

Walk through homework problems step-by-step from beginning to end. Hints help you try the next step on your own.

Wolfram Problem Generator »

Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet.

Wolfram Education Portal »

Collection of teaching and learning tools built by Wolfram education experts: dynamic textbook, lesson plans, widgets, interactive Demonstrations, and more.

Wolfram Language »

Knowledge-based programming for everyone.