TOPICS
Search

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

See also

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

Explore with Wolfram|Alpha

References

Dirac, G. "Some Theorems on Abstract Graphs." Proc. London Math. Soc. 2, 69-81, 1952.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.Li, H. "Generalizations of Dirac's Theorem in Hamiltonian Graph Theory--A Survey." Disc. Math. 313, 2034-2053, 2013.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 192, 1990.Yuan, L-.T. "Circumference, Minimum Degree and Clique Number." Elec. J. Combin. 31, No. 4, Article P4.64, 2024.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. https://mathworld.wolfram.com/GraphCircumference.html

Subject classifications