Reliability Analysis of Alternating Group Graphs and Split-Stars. (16th July 2020)

• Record Type: Journal Article
• Authors: Gu, Mei-Mei; Hao, Rong-Xia; Chang, Jou-Ming
• Is Part Of: Computer journal. Volume 64:Number 9(2021)
• Page Start: 1425
• Page End: 1436
• Publication Date: 2020-07-16
• Subjects: extra edge connectivity -- component edge connectivity -- generalized connectivity -- alternating group graphs -- split-stars; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxaa070
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: Given a connected graph $G$ and a positive integer $\ell $, the $\ell $ -extra (resp. $\ell $ -component) edge connectivity of $G$, denoted by $\lambda ^{(\ell )}(G)$ (resp. $\lambda _{\ell }(G)$ ), is the minimum number of edges whose removal from $G$ results in a disconnected graph so that every component has more than $\ell $ vertices (resp. so that it contains at least $\ell $ components). This naturally generalizes the classical edge connectivity of graphs defined in term of the minimum edge cut. In this paper, we proposed a general approach to derive component (resp. extra) edge connectivity for a connected graph $G$ . For a connected graph $G$, let $S$ be a vertex subset of $G$ for $G\in \{\Gamma _{n}(\Delta ), AG_n, S_n^2\}$ such that $|S|=s\leq |V(G)|/2$, $G[S]$ is connected and $|E(S, G-S)|=\min \limits _{U\subseteq V(G)}\{|E(U, G-U)|: |U|=s, G[U]\ \textrm{is connected}\ \}$, then we prove that $\lambda ^{(s-1)}(G)=|E(S, G-S)|$ and $\lambda _{s+1}(G)=|E(S, G-S)|+|E(G[S])|$ for $s=3, 4, 5$ . By exploring the reliability analysis of $AG_n$ and $S_n^2$ based on extra (component) edge faults, we obtain the following results: (i) $\lambda _3(AG_n)-1=\lambda ^{(1)}(AG_n)=4n-10$, $\lambda _4(AG_n)-3=\lambda ^{(2)}(AG_n)=6n-18$ and $\lambda _5(AG_n)-4=\lambda ^{(3)}(AG_n)=8n-24$ ; (ii) $\lambda _3(S_n^2)-1=\lambda ^{(1)}(S_n^2)=4n-8$, $\lambda _4(S_n^2)-3=\lambda ^{(2)}(S_n^2)=6n-15$ and $\lambda _5(S_n^2)-4=\lambda ^{(3)}(S_n^2)=8n-20$ . This general approach maybe applied to many diverse networks.