Generalized 4-connectivity of hierarchical star networks

Abstract

The connectivity is an important measurement for the fault-tolerance of a network. The generalized connectivity is a natural generalization of the classical connectivity. An SS-tree of a connected graph GG is a tree T=(V′,E′)T=\left(V^{\prime} ,E^{\prime} ) that contains all the vertices in SS subject to S⊆V(G)S\subseteq V\left(G). Two SS-trees TT and T′T^{\prime} are internally disjoint if and only if E(T)∩E(T′)=∅E\left(T)\cap E\left(T^{\prime} )=\varnothing and V(T)∩V(T′)=SV\left(T)\cap V\left(T^{\prime} )=S. Denote by κ(S)\kappa \left(S) the maximum number of internally disjoint SS-trees in graph GG. The generalized kk-connectivity is defined as κk(G)=min{κ(S)∣S⊆V(G)and∣S∣=k}{\kappa }_{k}\left(G)=\min \left\{\kappa \left(S)| S\subseteq V\left(G)\hspace{0.33em}\hspace{0.1em}\text{and}\hspace{0.1em}\hspace{0.33em}| S| \hspace{0.33em}=\hspace{0.33em}k\right\}. Clearly, κ2(G)=κ(G){\kappa }_{2}\left(G)=\kappa \left(G). In this article, we show that κ4(HSn)=n−1{\kappa }_{4}\left(H{S}_{n})=n-1, where HSnH{S}_{n} is the hierarchical star network.

Keywords

• hierarchical star networks
• fault-tolerance
• generalized connectivity
• disjoint s-trees
• 05c05
• 05c40
• 05c76