Cyclic Edge Connectivity

Let  be an edge cut of a connected graph . Then the cyclic edge connectivity  is the size of a smallest cyclic edge cut, i.e., a smallest edge cut  such that  has two connected components, each of which contains at least one graph cycle. Cyclic edge connectivity was considered as early as 1880 by Tait (1880).

A cyclic edge cut does not exist for all graphs. For example, a graph containing fewer than two cycles cannot have two components each of which contain a cycle. Examples of graphs having no cyclic edge cuts include the complete graphs  and , the utility graph , and the wheel graphs  (Dvorák et al. 2004). A graph for which no cyclic edge cut exists may be taken to have  (Lou et al. 2001).

The cyclic edge connectivity of the Petersen graph is  (Holton and Sheehan 1993, p. 86; Lou et al. 2001). This can be seen from the fact that removing the five "radial" edges leaves a disconnected inner pentagrammic cycle and outer pentagonal cycle.

Cyclic edge connectivity is most commonly encountered in the definition of snark graphs, which are defined as cubic cyclically 4-edge-connected graphs of girth at least 5 having edge chromatic number 4.

Plummer (1972) showed that a planar 5-connected graph has a cyclic edge connectivity of at most 13, while a planar 4-connected graph may have cyclic edge connectivity of any integer value 4 or larger. Borodin (1989) showed that the maximum cyclic edge connectivity of a 5-connected planar graph is at most 11.

The cyclic edge connectivity of a simple graph on  nodes satisfies

with equality for the complete graph when , i.e.,  for  (Lou et al. 2001).

---

REFERENCES

Borodin, O. V. "Solution of Kotzig's and Grünbaum's Problems on Separability of a Cycle in Planar Graphs." Mat. Zametki 46, 9-12, 1989.

Dvorák, Z.; Kára, J.; Král', D.; and Pangrác, O. "An Algorithm for Cyclic Edge Connectivity of Cubic Graphs." In Algorithm Theory--SWAT 2004 (Ed. T. Hagerup and J. Katajainen). Berlin: Springer, pp. 236-247, 2004.

Holton, D. A. and Sheehan, J. The Petersen Graph. Cambridge, England: Cambridge University Press, p. 86, 1993.

Lou, D.; Teng, L.; and Wu, S. "A Polynomial Algorithm for Cyclic Edge Connectivity of Cubic Graphs." Austral. J. Combin. 24, 247-259, 2001.

Plummer, M. D. "On the Cyclic Connectivity of Planar Graphs." In Graph Theory and Applications (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich., 1972). Berlin: Springer-Verlag, pp. 235-242, 1972.

Tait, P. G. "Remarks on the Colouring of Maps." Proc. Roy. Soc. Edingburg 10, 501-503, 1880.

اخر الاخبار

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

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

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

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

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

المزيد

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

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

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

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

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

المزيد

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

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

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

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

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

المزيد

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

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