错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Reliability analysis of the augmented cubes in terms of the h-extra r-component edge-connectivity

  • Yushen Zhang,
  • Mingzu Zhang,
  • Weihua Yang

摘要

In order to meet ever-increasing demands for reliable parallel and distributed systems, it is crucial to evaluate the reliability and fault tolerance of their underlying interconnection networks. Such an interconnection network is usually modeled as a connected graph G, where the vertex set and edge set represent the processors and links between processors in the network, respectively. In this paper, we combine Fàbrega’s idea about h-extra edge-connectivity and Sampathkumar’s concept about r-component edge-connectivity to introduce a more refined parameter for characterizing fault tolerance of interconnection networks, named as h-extra r-component edge-connectivity. Given a connected graph G, for two integers \(h\ge 1\) h 1 and \(r\ge 2\) r 2 , the h-extra r-component edge-connectivity of G, denoted as \(c\lambda _{r}^{h}(G)\) c λ r h ( G ) , is the minimum cardinality among all edge subsets \(F\subset E(G)\) F E ( G ) , if any, such that \(G-F\) G - F has at least r components, and each component has at least h vertices. As an enhancement on hypercube, the n-dimensional augmented cube \(\text {AQ}_n\) AQ n , introduced by Choudum and Sunitha in 2002, reserves several excellent topological properties. As \(|V(\text {AQ}_n)|=2^n\) | V ( AQ n ) | = 2 n , the h-extra three-component edge-connectivity of \(\text {AQ}_n\) AQ n is well-defined for each integer h with \(1\le h\le \lfloor 2^n/3 \rfloor\) 1 h 2 n / 3 . In this paper, a generalization of Xu et al.’s conclusion is obtained that finds an upper bound for the exact value of general h-extra three-component edge-connectivity of \(\text {AQ}_n\) AQ n and shows that it is sharp for \(1\le h\le 2^{\left\lfloor \frac{n}{2} \right\rfloor -1 }\) 1 h 2 n 2 - 1 and \(h=2^c\) h = 2 c where \(1\le c\le n-2\) 1 c n - 2 . Let \(h=\sum _{i=0}^{s} 2^{t_{i}}\) h = i = 0 s 2 t i be a positive integer with \(t_0> t_1> \cdots > t_s\ge 0\) t 0 > t 1 > > t s 0 . Let \(\delta =0\) δ = 0 if h is even and \(\delta =1\) δ = 1 if h is odd. Specifically, \(c\lambda _3^h(\text {AQ}_n)=(4n-4)h-2\sum _{i=0}^{s}(2 t_{i}-1) 2^{t_{i}}-2\sum _{i=0}^{s} 4i \cdot 2^{t_{i}}-\delta\) c λ 3 h ( AQ n ) = ( 4 n - 4 ) h - 2 i = 0 s ( 2 t i - 1 ) 2 t i - 2 i = 0 s 4 i · 2 t i - δ for \(n\ge 4, h\le 2^{\left\lfloor \frac{n}{2} \right\rfloor -1 }\) n 4 , h 2 n 2 - 1 , and \(c\lambda _3^{2^c}(\text {AQ}_n)=(2n-2c-1)2^{c+1}\) c λ 3 2 c ( AQ n ) = ( 2 n - 2 c - 1 ) 2 c + 1 for \(n\ge 4\) n 4 and \(1\le c\le n-2\) 1 c n - 2 .