Structure fault tolerance of balanced hypercubes
- PDF / 1,768,809 Bytes
- 14 Pages / 439.37 x 666.142 pts Page_size
- 79 Downloads / 186 Views
Structure fault tolerance of balanced hypercubes Yuxing Yang1 · Xiaohui Li1 · Jing Li2
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Let H be a connected subgraph of a given graph G. The H-structure connectivity of G is the cardinality of a minimal set F of subgraphs of G such that every element in F is isomorphic to H, and the removal of all the elements of F will disconnect G. The H-substructure connectivity of graph G is the cardinality of a minimal set F′ of subgraphs of G such that every element in F′ is isomorphic to a connected subgraph of H, and the removal of all the elements of F′ will disconnect G. The two parameters were proposed by Lin et al. in (Theor Comput Sci 634:97–107, 2016), where no restrictions on F and F′ . In Lü and Wu (Bull Malays Math Sci Soc 43(3):2659–2672, 2020), the authors imposed some restrictions on F (resp. F′ ) for the n-dimensional balanced hypercube BHn and requires that two elements in F (resp. F′ ) cannot share a vertex. Under such restrictions, they determined the (restricted) H-structure and (restricted) H-substructure connectivity of BHn for H ∈ {K1 , K1,1 , K1,2 , K1,3 , C4 } . In this paper, we follow (2016) for the definitions of the two parameters and determine the H-structure and H-substructure connectivity of BHn for H ∈ {K1,t , Pk , C4 } , where K1,t is the star on t + 1 vertices with 1 ≤ t ≤ 2n and Pk is a path of length k with 1 ≤ k ≤ 7 . Some of our main results show that the H-structure connectivity (resp. H-substructure connectivity) of BHn is equal to the restricted H-structure connectivity (resp. restricted H-substructure connectivity) of BHn for H ∈ {K1,1 , K1,2 , C4 } , but the K1,3-structure connectivity (resp. K1,3-substructure connectivity) of BHn is not equal to the restricted K1,3-structure connectivity (resp. restricted K1,3-substructure connectivity) of BHn unless n = ⌈2n∕3⌉. Keywords Interconnection networks · Balanced hypercubes · Structure fault tolerance · Structure connectivity · Substructure connectivity The third author of this paper is partly supported by Research Project of Shanxi Scholarship Council of China (No. 2020-122). * Yuxing Yang [email protected] 1
School of Mathematics and Information Science, Henan Normal University, Xinxiang 453007, Henan, China
2
School of Applied Science, Taiyuan University of Science and Technology, Taiyuan 030024, Shanxi, China
13
Vol.:(0123456789)
Y. Yang et al.
1 Introduction A multiprocessor system is constructed according to a certain graph where a vertex presents a processor and an edge presents the direct communicating link between a pair of processors. Such a graph is called the interconnection network of the multiprocessor system. The properties of an interconnection network determine the performance of the multiprocessor system. In multiprocessor systems, the faults of processors are inevitable. Therefore, network reliability becomes an issue in the area of interconnection networks. The connectivity 𝜅(G) of a graph G is the minimum number of vertices o
Data Loading...
