Conditional fault tolerance in a class of Cayley graphs

Abstract

Let G be a hierarchical network (graph) with vertex set $V(G)$ and edge set $E(G)$. The preclusion set of a subnetwork $G^{\prime }$ (defined as a smaller network but with the same topological properties as the original one) in G is a subset $V^{\ast }$ of $V(G)$ such that $G-V^{\ast }$ has no subnetwork $G^{\prime }$. The preclusion number of $G^{\prime }$ in G is $F(G^{\prime })=min\{|V^{\ast }|:V^{\ast }\text{is the preclusion set of}{G}^{\prime }\}$. Similarly, the edge preclusion set of $G^{\prime }$ in G is a subset $E^{\ast }$ of $E(G)$ such that $G-E^{\ast }$ has no subnetwork $G^{\prime }$. The edge preclusion number of $G^{\prime }$ in G is $f(G^{\prime })=min\{|E^{\ast }|:E^{\ast }\text{is the edge preclusion set of}{G}^{\prime }\}$. 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.

Keywords:

• interconnection network
• fault tolerance
• Cayley graph
• star graph
• bubble-sort graph
• preclusion number

2010 AMS Subject Classifications:

• 05C25
• 05C70
• 94C15
• 68M15
• 68R10

Acknowledgements

The authors would like to express their deepest gratitude to the anonymous referees for the constructive suggestions and comments that improve the quality of this paper.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Funding

This work is supported by the National Natural Science Foundation of China [grant numbers 61370001, 71171189] and the Doctoral Fund of Ministry of Education of China [grant numbers 20111401110005].