Conditional fault tolerance in a class of Cayley graphs
Mujiangshan Wang, Wenguo Yang, Yubao Guo, Shiying Wang · International Journal of Computer Mathematics · 2014
Let G be a hierarchical network (graph) with vertex set V(G) and edge set E(G). The preclusion set of a subnetwork G′ (defined as a smaller network but with the same topological properties as the original one) in G is a subset V∗ of V(G) such that G−V∗ has no subnetwork G′. The preclusion number of G′ in G is F(G′)=min{|V∗|:V∗ is the preclusion set of G′}. Similarly, the edge preclusion set of G′ in G is a subset E∗ of E(G) such that G−E∗ has no subnetwork G′. The edge preclusion number of G′ in G is f(G′)=min{|E∗|:E∗ is the edge preclusion set of G′}. The preclusion number and edge preclusion number are parameters which measure the robustness of interconnection networks in the event of failures. In this paper, we investigate a class of graphs which are constructed by combining the star graph with the bubble-sort graph, and give some preclusion numbers and edge preclusion numbers for this class of graphs.