ABSTRACT
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 is the cardinality of a minimum cyclic vertex cutset. In this paper, for any k-regular graph G with girth g and the number
of vertices, we give a sufficient condition
for the cyclic vertex connectivity
. Then we give a polynomial time algorithm to determine
for a cubic graph G. The time complexity of the algorithm is bounded by
.
Disclosure statement
No potential conflict of interest was reported by the author(s).
Notes
1. In [Citation3], Yefim Dinitz tells the differences between his version and Even's Version.