2019/04/13 by Zhao Wang, Wang, Zhao, Yaping Mao +3 · 2 citations
Computer Science · Materials Science · #Carbon and Quantum Dots Applications #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.1904.06527
openalex publication_date 2019/04/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Connectivity and diagnosability are two important parameters for the fault tolerant of an interconnection network G. In 1996, Fàbrega and Fiol proposed the g-extra connectivity of G. A subset of vertices S is said to be a cutset if G-S is not connected. A cutset S is called an Rg-cutset, where g is a non-negative integer, if every component of G-S has at least g+1 vertices. If G has at least one Rg-cutset, the g-extra connectivity of G, denoted by κg(G), is then defined as the minimum cardinality over all Rg-cutsets of G. In this paper, we first obtain the exact values of g-extra connectivity of some special graphs. Next, we show that 1≤ κg(G)≤ n-2g-2 for 0≤ g≤ \lfloor (n-3)/(2)\rfloor, and graphs with κg(G)=1,2,3 and trees with κg(Tn)=n-2g-2 are characterized, respectively. In the end, we get the three extremal results for the g-extra connectivity.