TOPICS
Search

Cyclic Edge Cut


A cyclic edge cut of a graph is an edge cut such that at least two of the resulting connected components each contain at least one cycle. In a connected graph, each minimum cyclic edge cut splits the graph into exactly two components. In a disconnected graph with at least two components that each contain at least one cycle, the empty set of edges comprises a trivial cyclic edge cut.

A cyclic edge cut of smallest possible size in a given graph is called a minimum cyclic edge cut.

CyclicEdgeCuts

The cyclic edge cuts of two distinct types for the Petersen graph P are illustrated above. Each involves five edges, so the cyclic edge connectivity is lambda_c(P)=5.

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 cyclic edge connectivity lambda_c=0 (Lou et al. 2001).

CyclicEdgeCutSmallestGraphs

The smallest graph that possesses a cyclic edge cut must contain two triangles (and therefore 6 vertices) connected by a single edge (therefore having a total of 7 edges). The graph so constructed is precisely the 3-barbell graph. There are two next smallest graphs possessing a cyclic edge cut, each having 6 vertices and 8 edges. These graphs are illustrated above.


See also

Cyclic Edge Connectivity, Minimum Cyclic Edge Cut

Explore with Wolfram|Alpha

References

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

Cite this as:

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

Subject classifications