TOPICS
Search

Cyclic Edge Connectivity

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

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

Note that Grünbaum (2003, p. 365) and others use the term "cyclically k-connected" (omitting in the word "edge") to refer to a graph that cannot be broken into two separate parts each of which contains a cycle by an edge cut of fewer than k edges.

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 wheel graphs W_n (Dvorák et al. 2004). A graph for which no cyclic edge cut exists may be taken to have lambda_c=0 (Lou et al. 2001).

CyclicEdgeConnectivityPetersenGraph

The cyclic edge connectivity of the Petersen graph is lambda_c(P)=5 (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.

Birkhoff (1913) reduced the four-color problem to cyclically 5-edge-connected polyhedral graphs (Grünbaum 2003, p. 365). Hunter (1962) conjectured that such graphs are all Hamiltonian, but this was refuted with the discovery of the 162-vertex cubic nonhamiltonian 162-vertex Walther graph (Walther 1965, Grünbaum 2003, p. 365).

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 n nodes satisfies

lambda_c(G)<=3(n-3)

with equality for the complete graph when n>=6, i.e., lambda_c(K_n)=3(n-3) for n>=6 (Lou et al. 2001).

See also

Cyclic Edge Cut, Edge Connectivity, Edge Cut, Minimum Cyclic Edge Cut, Snark

Explore with Wolfram|Alpha

References

Birkhoff, G. D. "The Reducibility of Maps." Amer. J. Math 35, 115-128, 1913.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.Grünbaum, B. Convex Polytopes, 2nd ed. New York: Springer-Verlag, 2003.Holton, D. A. and Sheehan, J. The Petersen Graph. Cambridge, England: Cambridge University Press, p. 86, 1993.Hunter, H. F. On Non-Hamiltonian Maps and their Duals. Ph. D. thesis. Troy, NY: Rensselaer Polytechnic Institute, 1962.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.Walther, H. "Ein kubischer, planarer, zyklisch fünffach zusammenhängender Graf, der keinen Hamiltonkreis besizt." Wiss. Z. Hochschule Elektrotech. Ilmenau 11, 163-166, 1965.

Cite this as:

Weisstein, Eric W. "Cyclic Edge Connectivity." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/CyclicEdgeConnectivity.html

Subject classifications