A polynomial time algorithm for cyclic vertex connectivity of cubic graphs

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 $c\kappa \left(G\right)$ 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\ge 2g(k-1)$ for the cyclic vertex connectivity $c\kappa \left(G\right)\ne \mathrm{\infty }$. Then we give a polynomial time algorithm to determine $c\kappa \left(G\right)$ for a cubic graph G. The time complexity of the algorithm is bounded by $O\left(v^{15/2}\right)$.

KEYWORDS:

• Cyclic vertex connectivity
• maximum flow
• computational complexity
• cubic graph

2010 AMS SUBJECT CLASSIFICATIONS:

• 05C40
• 05C38
• 68R10

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1. In [3], Yefim Dinitz tells the differences between his version and Even's Version.

Additional information

Funding

This research is partially supported by the China Scholarship Council [grant number 201508440189], and NSFC [grant number 11471003].