A polynomial time algorithm for cyclic vertex connectivity of cubic graphs
Jun Liang, Dingjun Lou, Zan‐Bo Zhang · International Journal of Computer Mathematics · 2016
For a connected graph G, a set S of vertices is a cyclic vertex cutset if G−S is not connected and at least two components contain a cycle respectively. The cyclic vertex connectivity cκ(G) is the cardinality of a minimum cyclic vertex cutset. In this paper, for any k-regular graph G with girth g and the number v of vertices, we give a sufficient condition v≥2g(k−1) for the cyclic vertex connectivity cκ(G)≠∞. Then we give a polynomial time algorithm to determine cκ(G) for a cubic graph G. The time complexity of the algorithm is bounded by O(v15/2).