| With the rapid development of information networks, reliability of networks comeinto focus, that is, the ability of the network to function even when some vertices and/oredges fail. The underlying topology of a network is often modeled as a graph. Assumethat in G edges are reliable and each vertex fails independently with the same probabilityÏ∈(0,1). Then the probability of G being disconnected iswhere n is the order of G, ni(G) is the number of i-vertex cut of G,κis the connectivityof G. We call UR(G) the vertex unreliability polynomial of G.Some classical parameters of graph theory, such as the connectivity and the edge-connectivity, are utilized to measure the reliability of networks. For further study, manyvariations have been introduced, which are known as higher order connectedness, such assuper-κ, k-restricted connectivity, etc. A vertex subset F is a k-restricted vertex-cut ofa connected graph G if G ? F is disconnected and every vertex in G ? F has at least kgood neighbors in G ? F. The cardinality of the minimum k-restricted vertex-cut of G isthe k-restricted connectivity of G, denoted byκk(G). This parameter measures a kind ofconditional fault tolerance of networks.Alternating group graphs have been shown to have many desirable properties suchas strong hierarchy, high connectivity, small diameter and average distance, etc., whichmakes it favorable as a network topology.This thesis is divided into three chapters. In Chapter 1, we introduce the backgroundof our study. Then we state the main results in this thesis. In Chapter 2, we obtain arecurrence formula for the unreliability polynomial of graphs. Then, the unreliability poly-nomials of some special classes of graphs are determined by using this formula, includingcomplete graph, star, the join of a complete graph and an empty graph, complete bipar-tite graph, path, and cycle. In Chapter 3, we show that for the n-dimensional alternatinggroup graph AGn,κ1(AG4) =κ2(AG4) = 4, andκ1(AGn) = 4n - 11,κ2(AGn) = 6n - 18for n≥5.
|
PDF Full Text Request