Cyclic vertex-connectivity of Cartesian product graphs. Issue 1 (2nd January 2020) - Qin, Dejin; Tian, Yingzhi; Chen, Laihuan; Meng, Jixiang
Abstract : A cyclic vertex-cut of a graph G is a vertex set S such that G − S is disconnected and at least two of its components contain cycles. If G has a cyclic vertex-cut, then it is said to be cyclically separable. For a cyclically separable graph G, the cyclic vertex-connectivity κ c ( G ) is defined as the cardinality of a minimum cyclic vertex-cut. Let G i be a k i -regular ( k i ≥ 2 ) and maximally connected graph with girth g ( G i ) ≥ 5 for i =1, 2. In this paper, we mainly prove that κ c ( K m ◻ G 2 ) = 3 k 2 + m − 3 for m ≥ 3 and κ c ( G 1 ◻ G 2 ) = 4 k 1 + 4 k 2 − 8 . In addition, we state sufficient conditions to guarantee κ c ( K 2 ◻ G 2 ) = 2 κ ( G 2 ) .