A polynomial algorithm determining cyclic vertex connectivity of k-regular graphs with fixed k

摘要

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 of G - S contain a cycle respectively. The cyclic vertex connectivity C kappa (G) is the cardinality of a minimum cyclic vertex cutset. In this paper, for a k-regular graph G with fixed k value, we give a polynomial time algorithm to determine oc(G) and its time complexity is bounded by O (v(15/2)).