تسجيل الدخول

تسجيل

Graph Circumference

المؤلف:  Farrugia, A

المصدر:  "Self-Complementary Graphs and Generalisations: a Comprehensive Reference Manual." Aug. 1999. http://www.alastairfarrugia.net/sc-graph/sc-graph-survey.pdf.

الجزء والصفحة:  ...

23-4-2022

2670

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	{n^2/2 for n even; (n^2+1)/2 for n odd" src="https://mathworld.wolfram.com/images/equations/GraphCircumference/Inline10.svg" style="height:69px; width:220px" />
book graph	6
complete bipartite graph  for
-cone graph	{2m for m<=n; m+n otherwise" src="https://mathworld.wolfram.com/images/equations/GraphCircumference/Inline16.svg" style="height:61px; width:153px" />
gear graph
grid graph	{mn-1 for m,n odd; mn otherwise" src="https://mathworld.wolfram.com/images/equations/GraphCircumference/Inline19.svg" style="height:61px; width:196px" />
grid graph	{lmn-1 for l,m,n odd; lmn otherwise" src="https://mathworld.wolfram.com/images/equations/GraphCircumference/Inline21.svg" style="height:61px; width:244px" />
helm graph
-knight graph	{14 for n=4; n^2 for even n>4; n^2-1 for odd n>2" src="https://mathworld.wolfram.com/images/equations/GraphCircumference/Inline24.svg" style="height:93px; width:200px" />
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.