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.

اخر الاخبار

اخبار العتبة العباسية المقدسة

عضو مجلس إدارة العتبة العباسية المقدسة يطلع على آليات تطوير البرامج التعليمية في مجموعة العميد

مجموعة مناحل الكفيل تختتم مشاركتها في معرض السليمانية الدولي للزراعة والصناعات الغذائية

لتوثيق التراث العلمي.. وفد قسم شؤون المعارف يلتقي عددًا من أعلام مدينة النجف

قسم الشؤون الفكرية ومؤسسة الشهداء يبحثان سبل تعزيز التعاون في برامج الذاكرة الوطنية

المزيد

الآخبار الصحية

طبيب يكشف تأثير برودة الشتاء على النوم

دون أن تعلم.. 10 عادات يومية تسرع شيخوخة جسمك

تقرير: النيكوتين خطر على القلب مهما كانت الطريقة

أيهما أفضل لصحتك.. زبدة الفول السوداني أم النوتيلا؟

المزيد

الآخبار التكنلوجية

السعودية تدشن أكبر نظام لتخزين الكهرباء بالبطاريات في العالم !

بأمر تنفيذي.. ترامب يؤكد هدف عودة الأميركيين إلى القمر في عام 2028

بعيدا عن البشر.. "قتال جوي في الفضاء" بين أميركا والصين

كشف مذهل في قاع "برمودا" !

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength