科研之友
微信
新浪微博
Facebook
分享链接
摘要
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) not equal 8. 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(v(15/2)).
- 出版日期2017-7
- 单位中山大学
