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
2176
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 |
![<span style=]() {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 |
![<span style=]() {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  |
![<span style=]() {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  |
![<span style=]() {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 |
![<span style=]() {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.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
