Conditional Connectivity And Restricted Diagnosability Of Some Regular Graphs

Bijective connection networks(also called BC graphs),k-ary n-cubes and star graphs are three kinds of regular graphs,which are widely applied as the topology of interconnection net-works of parallel computer systems.The connectivity and diagnosability are important parame-ters to measure the reliability of interconnection networks.The g-extra connectivity,the g-extra diagnosability,the g-good neighbour connectivity and the g-good neighbour diagnosability are two kinds of connectivity and diagnosability with some restricted conditions,which receive a lot of attractions because they can measure the reliability of interconnection networks more precisely.In this paper,we study the g-extra connectivity,the g-extra diagnosability,the g-good neighbour connectivity and the g-good neighbour diagnosability of BC graphs,k-ary n-cubes and hierarchi-cal star graphs,which take star graphs as the units.These research can provide theoretical basis for the reliability analysis and design of fault diagnosis algorithm of computer systems with these graphs as their topology of interconnection networks.For BC graphs,the g-extra diagnosability of BC graphs and folded hypercubes intimately related to BC graphs,is researched under the PMC model and MM*model.The g-extra diag-nosability of a graph G is the maximal cardinality of fault vertices by a self-diagnosis,under the condition that requires every fault-free component contains at least(g+1)vertices.Making use of the properties of the subgraphs of BC graphs with order(g+1),we show a lower bound of the g-extra diagnosability of BC graphs and provide some sufficient conditions satisfying the lower bound.Furthermore,for a general integer g,we obtain the g-extra diagnosability of n-dimensional hypercubes and varietal hypercubes;for small g(1 ?g ?3),the g-extra diagnosability of BC graphs is determined.Finally,we present the g-extra diagnosability of folded hypercubes under the MM*model.For k-ary n-cubes,we investigate the g-extra connectivity and the g-extra diagnosability of k-ary n-cubes under the PMC and MM*models.The g-extra connectivity of G is defined as the cardinality of the smallest vertex subset F such that G-F is disconnected and every component of G-F contains at least(g+1)vertices.First,we discuss the properties of the subgraphs of k-ary n-cubes with order(g+1)in detail,and determine the g-extra connectivity of k-ary n-cubes.On this basis,making use of the relationship between the g-extra connectivity and the g-extra diagnosability,we obtain the g-extra diagnosability of k-ary n-cubes under the PMC model and MM*model.For hierarchical star graphs,we investigate the g-good neighbour connectivity and the g-good neighbour diagnosability of hierarchical star graphs under the PMC and MM*models.The g-good neighbour connectivity of G is defined as the cardinality of the smallest vertex subset F such that G-F is disconnected and the minimum degree of every component of G-F is at least g.First,we investigate the the properties of the subgraphs of star graphs and hierarchical star graphs with the minimum degree not less than g in detail,and determine the g-good neighbour connectivity of hierarchical star graphs.Furthermore,making use of the relationship between the g-good neighbour connectivity and the g-good neighbour diagnosability,we present the g-good neighbour diagnosability of hierarchical star graphs under the PMC and MM*models.