Cyclic vertex-connectivity of Cartesian product graphs. Issue 1 (2nd January 2020)

• Record Type: Journal Article
• Authors: Qin, Dejin; Tian, Yingzhi; Chen, Laihuan; Meng, Jixiang
• Is Part Of: International journal of parallel, emergent and distributed systems. Volume 35:Issue 1(2020)
• Page Start: 81
• Page End: 90
• Publication Date: 2020-01-02
• Subjects: Cyclic vertex-cut -- cyclic vertex-connectivity -- cartesian product -- maximally connected; Parallel computers -- Periodicals; Electronic data processing -- Distributed processing -- Periodicals; Computer algorithms -- Periodicals; 004.35
• DOI: 10.1080/17445760.2019.1659259
• Languages: English
• ISSNs: 1744-5760

Abstract

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 ) .