Component connectivity of Cayley graphs generated by transposition trees. Issue 1 (2nd January 2020)

• Record Type: Journal Article
• Authors: Xu, Liqiong; Zhou, Shuming; Yang, Weihua
• Is Part Of: International journal of parallel, emergent and distributed systems. Volume 35:Issue 1(2020)
• Page Start: 103
• Page End: 110
• Publication Date: 2020-01-02
• Subjects: Interconnection network -- component connectivity -- component edge connectivity -- Cayley graph -- fault tolerance; Parallel computers -- Periodicals; Electronic data processing -- Distributed processing -- Periodicals; Computer algorithms -- Periodicals; 004.35
• DOI: 10.1080/17445760.2019.1618462
• Languages: English
• ISSNs: 1744-5760

Abstract

ABSTRACT: Connectivity is an important measure to explore the fault tolerance and reliability of the network structure based on a graph model. Let G = ( V, E ) be a connected graph. A r -component cut of G is a set S of vertices, G − S has at least r components. The r -component connectivity c κ r ( G ) of G is the size of the smallest r -component cut. The r -component edge connectivity c λ r ( G ) can be defined similarly. In this paper, we determine the r -component connectivity of Cayley graphs generated by transposition trees c κ r + 1 ( T n ) = r ( n − 1 ) − r ( r + 1 ) / 2 + 1 for r = 1, 2, …, n − 1 and n ≥ 3 ; we also obtain the r -component edge connectivity of Cayley graphs generated by transposition trees T n for small r and the upper and lower bounds of c λ r + 1 ( T n ) for r = 1, 2, …, n − 1 and n ≥ 3 .