Reliability Assessment of Some Regular Networks. (15th November 2019)

• Record Type: Journal Article
• Authors: Zhao, Shu-Li; Hao, Rong-Xia; Peng, Sheng-Lung
• Editors: Stewart, Iain
• Is Part Of: Computer journal. Volume 64:Number 1(2021)
• Page Start: 1
• Page End: 6
• Publication Date: 2019-11-15
• Subjects: interconnection network -- generalized connectivity -- fault-tolerance -- internally disjoint trees; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxz116
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: The generalized $k$ -connectivity of a graph $G$ is a parameter that can measure the reliability of a network $G$ to connect any $k$ vertices in $G$, which is a generalization of traditional connectivity. Let $S\subseteq V(G)$ and $\kappa _{G}(S)$ denote the maximum number $r$ of edge-disjoint trees $T_{1}, T_{2}, \cdots, T_{r}$ in $G$ such that $V(T_{i})\bigcap V(T_{j})=S$ for any $i, j \in \{1, 2, \cdots, r\}$ and $i\neq j$ . For an integer $k$ with $2\leq k\leq n$, the generalized $k$ -connectivity of a graph $G$ is defined as $\kappa _{k}(G)= min\{\kappa _{G}(S)|S\subseteq V(G)$ and $|S|=k\}$ . In this paper, we introduce a family of regular graph $G_{n}$ that can be constructed recursively and each vertex with exactly one outside neighbor. The generalized $3$ -connectivity of the regular graph $G_{n}$ is studied, which attains a previously proven upper bound on $\kappa _{3}(G)$ . As applications of the main result, the generalized $3$ -connectivity of some important networks including some known results such as the alternating group network $AN_{n}$, the star graph $S_{n}$ and the pancake graphs $P_{n}$ can be obtained directly.