A polynomial algorithm for cyclic edge connectivity of cubic graphs (Q2760446)

The authors discuss the cyclic edge connectivity of cubic graphs. The cyclic edge connectivity \(\lambda(G)\) is the minimum cardinality of all the cyclic edge cutsets of a graph \(G\). A cyclic edge cutsets of a graph \(G\) is an edge cutset whose deletion disconnects the graph \(G\) such that each of the two components created must contain at least one cycle.NEWLINENEWLINENEWLINEThe authors, after having mentioned some studies on the concept of cyclic edge connectivity, developed a recursive algorithm to find all cyclic edge cutsets of a cubic graph, with time complexity bounded by \(O(n^3\log_2n)\). They describe their algorithm as follows:NEWLINENEWLINENEWLINEFirst they study the trivial cases, namely (1) if \(G\) is isomorphic to \(K_4\), then \(G\) has no cyclic edge cutsets, and (2) if \(G\) is not 3-connected, then it is 1- or 2-connected. By Lemma 3, the cyclic edge connectivity is 1 or 2, respectively. All cyclic edge cutsets can be found by checking all minimum vertex cutsets.NEWLINENEWLINENEWLINE If \(G\) is 3-connected and \(G\) is not \(K_4\), then an edge \(e\) is removed from \(G\) (cases how to remove edge \(e\) are studied): (i) if \(G-e\) is 3-connected, the program is called recursively with \(G-e\), and (ii) if \(G-e\) is 2-connected, then in the next recursive step the minimum cyclic edge cutsets of \(G-e\) will be returned, and then those of \(G\).NEWLINENEWLINENEWLINEThe authors finish by proving the validity of their algorithm and by application of it on the Petersen graph which is 3-regular and 3-connected.NEWLINENEWLINENEWLINEThe paper is well written and the result is interesting. It contributes to the development of graph edge connectivity theory to some degree.