Cyclic vertex-connectivity of Cartesian product graphs

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 ${\kappa }_c\left(G\right)$ is defined as the cardinality of a minimum cyclic vertex-cut. Let $G_i$ be a $k_i$-regular $(k_i\ge 2)$ and maximally connected graph with girth $g\left(G_i\right)\ge 5$ for i=1,2. In this paper, we mainly prove that ${\kappa }_c\left(K_m◻G_2\right)=3k_2+m-3$ for $m\ge 3$ and ${\kappa }_c\left(G_1◻G_2\right)=4k_1+4k_2-8$. In addition, we state sufficient conditions to guarantee ${\kappa }_c\left(K_2◻G_2\right)=2\kappa \left(G_2\right)$.

Keywords:

• Cyclic vertex-cut
• cyclic vertex-connectivity
• cartesian product
• maximally connected

Acknowledgements

We would like to thank the anonymous referee for their valuable suggestions which helped us a lot in improving the presentation of this paper.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

Foundation item: The research is supported by National Natural Science Foundation of China (NSFC) [grant number 11531011].