Research On The Reliability Of Some Special Graphs

Network reliability, a key factor to measure networks performance, has alwaysbeen a rich topic for the researchers around the world, and in recent years, its theoryhas been applied extensively in many real-world systems such as computer andcommunication systems, power transmission and distribution systems, traffic andtransportation systems etc. Thus, network reliability plays important roles in ourmodem society.Most real-world systems including described above can be modeled by networksor graphs which are composed of generalized nodes and edges, where nodes denotethe elements and edges represent the relations between two elements. Although thedefinition of networks or graphs is simple, they can show up extraordinarycomplexities.Currently, there are two primary methods on the research about networkreliability, one of which based on the determinacy theory with some reasonableinvariants was adopted in this paper, the other grounded on the probability theory.At first, network reliability researches with determinacy theory mainly focusedon the vertex-connectivity and edge-connectivity, but as the researches progressingand advancing, people found that these two parameters only taken into account thehardness to destroy the networks or graphs, but not the extent to which they weredamaged. Therefore, some new parameters and their variants were introduced, ofwhich vertex-toughness and vertex-tenacity being thought highly two betterparameters to evaluate network reliability.Indeed, the topological structure of network dominated its reliability, and in theworst case, most network reliability problems are NP-hard, to some extent moredifficult than many standard combinatorial optimization problems, hence it'svaluable to discuss and compute the reliability of special graphs. In this paper, thevertex-toughness and vertex-tenacity of some special graphs are given and proved.