A Kind of Conditional Connectivity of Cayley Graphs Generated by 2-trees. (25th October 2017)

• Record Type: Journal Article
• Authors: Xu, Liqiong; Zhou, Shuming; Lian, Guanqin; Luo, Zuwen
• Is Part Of: Computer journal. Volume 61:Number 5(2018)
• Page Start: 714
• Page End: 721
• Publication Date: 2017-10-25
• Subjects: 2-tree -- Cayley graphs -- conditional connectivity; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxx100
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: For a connected graph G = ( V ( G ), E ( G ) ), a subset F ⊂ V ( G ) is called an R k -vertex-cut if G − F is disconnected and each vertex u ∈ V ( G ) − F has at least k neighbors in G − F . The cardinality of a minimum R k -vertex-cut of G is the R k -vertex-connectivity and is denoted by κ k ( G ) . The conditional connectivity is a new measure to study the fault tolerance of network structures beyond connectivity. In this paper, we study R 1 -vertex-connectivity and R 2 -vertex-connectivity of Cayley graphs generated by 2-trees T 2, n, which are denoted by K T n, and show that κ 1 ( K T n ) = 4 n − 8 for n ≥ 4 ; κ 2 ( K T n ) = 8 n − 22 for n ≥ 6 .