International Journal of Computer Mathematics · 2014 · 19 citations · 14 references
ComputingComputer ScienceMathematicsFault ToleranceFault-tolerant ComputingInterconnection NetworksDirected Acyclic GraphsGraph AlgorithmsGraph TheoryNetwork RobustnessNetwork StructureNetwork TopologyBubble SortFault-tolerant Interconnection NetworksGraph Theory In NetworksGraph-theoretic Network AnalysisHierarchical Network StructureInterconnection Network Reliability
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.
14
Conditional matching preclusion sets
Eddie Cheng, Linda Lesniak, Marc J. Lipman et al. · Information Sciences · 2008 · 105 citations
Matching preclusion for some interconnection networks
Eddie Cheng, László Lipták · Networks · 2007 · 89 citations · Full text
Bernd Becker, Hans Ulrich Simon · 1986 · 69 citations
Shiying Wang, Ruixia Wang, Shangwei Lin et al. · Discrete Applied Mathematics · 2010 · 68 citations