The Generalized Three-Connectivity of Two Kinds of Cayley Graphs. (26th May 2018)

• Record Type: Journal Article
• Authors: Zhao, Shu-Li; Hao, Rong-Xia
• Editors: Stewart, Iain
• Is Part Of: Computer journal. Volume 62:Number 1(2019)
• Page Start: 144
• Page End: 149
• Publication Date: 2018-05-26
• Subjects: generalized connectivity -- fault-tolerance -- Cayley graph -- complete graph -- wheel graph; Computers -- Periodicals; 005.1
• DOI: 10.1093/computer_journal/bxy054
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: Let S ⊆ V ( G ) and κ G ( S ) denote the maximum number r of edge-disjoint trees T 1, T 2, …, T r in G such that V ( T i ) ∩ V ( T j ) = S for any i, j ∈ { 1, 2, …, r } and i ≠ j . For an integer k with 2 ≤ k ≤ n, the generalized k-connectivity of a graph G is defined as κ k ( G ) = min { κ G ( S ) | S ⊆ V ( G ) and | S | = k } . The generalized k -connectivity is a generalization of traditional connectivity. In this paper, we focus on the Cayley graph generated by complete graphs and the Cayley graph generated by wheel graphs, denoted by C T n and W G n, respectively. We study the generalized 3-connectivity of the two kinds of graphs and show that κ 3 ( C T n ) = n ( n − 1 ) 2 − 1 and κ 3 ( W G n ) = 2 n − 3 for n ≥ 3 .