Chordless Cycle

A chordless cycle of a graph  is a graph cycle in  that has no cycle chord. Unfortunately, there are conflicting conventions on whether or not 3-cycles should be considered chordless. In particular, in mathematical graph theory, "trivial" cycles of length 3 are commonly not considered chordless (e.g., West 2000), while in computer science, length-3 cycles are generally considered chordless (e.g., Cook 2000, Wikipedia 2020). For example, (West 2000, p. 225) states, "A chordless cycle in  is a cycle of length at least 4 in  that has no chord (that is, the cycle is an induced subgraph), while Cook (2000, p. 197) states, "a triangle is considered to be a chordless cycle."

Excluding 3-cycles allows for simpler definitions and theorem statements (particularly those related to perfect graphs), for example permitting the definition of chordal graph as a simple graph possessing no chordless cycles (West 2000, p. 225) without further qualification.

The "ChordlessCycles" and related properties in the Wolfram Language function GraphData adopt the convention of West (2000, p. 225) that chordless cycles must have length at least 4.

An alternate approach followed by Chvátal defines a graph hole as "a chordless cycle of length at least four," thus distinguishing between the a generic "chordless cycle" (possibly allowing length-3 cycles) and a "hole" (excluding them).

Since the term "chordless cycle" seems to be used much more widely than "graph hole," perhaps the clearest approach is to always state "chordless cycle of length at least four" when length-3 cycles are to be excluded.

A graph is perfect iff neither the graph nor its complement has a (length four or greater) chordless cycle of odd order.

If a chordless 5-cycle exists in a graph , one also exists in its graph complement  since in the complement the interior diagonals are really edges in the original. In addition, if no 5-cycle exists in , then no chordless cycle exists in  (S. Wagon,. pers. comm., Feb. 2013).

No chordless cycles (of length four or more) of length greater than  exist in a graph  with independence number .

No chordless cycles (of length four or more) of length greater than  exist in the graph complement  of a graph  with , where  is the clique covering number and  is the clique number.

Every cycle of a cactus graph is chordless, but there exist graphs (e.g., the -graph and Pasch graph) whose cycles are all chordless but which are not cactus graphs.

---

REFERENCES

Cook, K.; Eschen, E. M.; Sritharan, R.; and Wang, X. "Completing Colored Graphs to Meet a Target Property." In Graph-Theoretic Concepts in Computer Science: 39th International Workshop, WG 2013, Lübeck, Germany, June 19-21, 2013, Revised Papers.Ed. A. Brandstädt, K. Jansen, and R. Reischuk). Berlin, Germany:ÊSpringer, pp. 189-200, 2013.

Chvátal, V. "The Strong Perfect Graph Theorem." http://www.cs.concordia.ca/~chvatal/perfect/spgt.html.

West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, p. 225, 2000.

Wikipedia contributors. "Induced Path." Wikipedia, The Free Encyclopedia. Wikipedia, The Free Encyclopedia. Aug. 7, 2020; retreived Sep. 4, 2020. https://en.wikipedia.org/wiki/Induced_path.

اخر الاخبار

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

سماحة السيد الصافي يكرم عددًا من عوائل الشهداء ضمن فعاليات مهرجان روح النبوة النسوي العالمي الثامن

إحدى أمهات الشهداء: نعتز بتضحيات أبنائنا ونفتخر بشهادتهم دفاعًا عن الدين والمقدسات

ضمن فعاليات مهرجان روح النبوة… عرض فيلم يوثق نشاطات الشعب النسوية في العتبة العباسية المقدسة

فعاليات مهرجان روح النبوة الثقافي تشهد تقديم أوبريت الثقلين القرآني

المزيد

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

ماذا يحدث لجسمك عند تناول الوجبات السريعة يوميا؟

لصحة عظام المرأة.. الشاي أفضل أم القهوة؟

لبناء العضلات وإنقاص الوزن.. ما أفضل توقيت لتناول البيض؟

أطعمة صحية تساعد على التعافي من "الإنفلونزا الخارقة"

المزيد

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

دراسة تكشف قدرة الحيتان على سماع الأصوات منخفضة وعالية التردد من مسافة بعيدة

تجربة جديدة: الأسفلت المدعوم بالطحالب يقاوم الحفر ويقلل الانبعاثات الكربونية

تسريبات تكشف ملامح أول هاتف قابل للطي من "أبل"

رصد نوع نادر من القطط في تايلاند للمرة الأولى منذ عقود

المزيد

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

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