On conditional connectivity of the Cartesian product of cycles

2020/01/31 by J. B. Saraf, Y. M. Borse, Saraf, J. B. +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Interconnection Networks and Systems

paper · pdf · doi:10.48550/arxiv.2001.11781

openalex publication_date 2020/01/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The conditional h-vertex(h-edge) connectivity of a connected graph H of minimum degree k > h is the size of a smallest vertex(edge) set F of H such that H - F is a disconnected graph of minimum degree at least h. Let G be the Cartesian product of r≥ 1 cycles, each of length at least four and let h be an integer such that 0≤ h≤ 2r-2. In this paper, we determine the conditional h-vertex-connectivity and the conditional h-edge-connectivity of the graph G. We prove that both these connectivities are equal to (2r-h)a_h^r, where a_h^r is the number of vertices of a smallest h-regular subgraph of G.

Related

• Two bounds for generalized 3-connectivity of Cartesian product graphs
• The g-extra connectivity of the strong product of paths and cycles
• A characterization of the edge connectivity of direct products of graphs
• Mixed connectivity of Cartesian graph products and bundles
• On Linkedness of Cartesian Product of Graphs