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.

اخر الاخبار

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

جولة تفقدية لمتابعة خطة تنظيم مداخل المعزّين المشاركين في عزاء ركضة طويريج

لتعزيز التعاون الأكاديمي والبحثي.. جامعة الكفيل توقع اتفاقيتي توأمة مع جامعتين عراقيتين

المجمَع العلميّ يواصل إقامة مجلسه العزائي بذكرى شهادة الإمام الحسين (عليه السلام) في النجف الأشرف

قسم حفظ النظام يواصل تنفيذ خطته لتنظيم سير المواكب والزائرين في شهر المحرم

المزيد

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

لهذا السبب.. إغلاق 25 مركزًا لعلاج الإدمان في مصر ؟

خلافا للاعتقاد الشائع.. علماء يكشفون أسرار بذور البطيخ ؟!

هذا ما يحدث لجسمك عند تناولك الطماطم بانتظام !

تعرف على أطعمة تسرّع "تعافي الجسم" من حروق الشمس

المزيد

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

الثلوج تغطي الصحراء الأكثر جفافا في العالم!

بتلسكوب "ألما".. التقاط صورا غير مسبوقة لبدايات الكون !

هل هاتفك مراقب؟.. 5 علامات خطيرة تكشف التجسس عليك

دبي تطلق أول رحلة تجريبية للتاكسي الجوي

المزيد

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

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