Cyclic vertex-connectivity of Cartesian product graphs
Dejin Qin, Yingzhi Tian, Laihuan Chen, Jixiang Meng · International Journal of Parallel Emergent and Distributed Systems · 2019
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 Gi be a ki-regular (ki≥2) and maximally connected graph with girth g(Gi)≥5 for i=1,2. In this paper, we mainly prove that κc(Km◻G2)=3k2+m−3 for m≥3 and κc(G1◻G2)=4k1+4k2−8. In addition, we state sufficient conditions to guarantee κc(K2◻G2)=2κ(G2).