151
Views
14
CrossRef citations to date
0
Altmetric
Original Articles

Conditional fault tolerance in a class of Cayley graphs

, , &
Pages 67-82 | Received 08 Jan 2014, Accepted 11 Nov 2014, Published online: 20 Dec 2014
 

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 (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 GV 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 GE 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.

2010 AMS Subject Classifications:

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].

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.