LAUSR

For a connected graph G, a set S of vertices is a cyclic vertex cutset if $$G - S$$G-S is not connected and at least two components of $$G-S$$G-S contain a cycle respectively. The cyclic vertex connectivity $$c \kappa (G)$$cκ(G) is the cardinality of a minimum cyclic vertex cutset. In this paper, for a 4-regular graph G with v vertices, we give a polynomial time algorithm to determine $$c \kappa (G)$$cκ(G) of complexity $$O(v^{15/2})$$O(v15/2).