Symmetry And Fault-tolerant Analysis Of Graphs

A graph is symmetric (or arc-transitive) if its automorphism group is transitive on the arc set of the graph. Symmetric graphs, especially symmetric graphs of small va-lency, are often used to design interconnection networks. Element failure is inevitable when an interconnection network is put in use. This forces that a network should have better fault-tolerant capacity. Some definitions and properties of graphs can be used to evaluate the fault-tolerance of networks effectually. This thesis investigates connected symmetric graphs of valency five and fault-tolerant analysis of two interconnection net-works based on symmetric graphs.This thesis is organized as follows.Chapter 1 is an introduction part. We introduce some basic definitions of finite group theory and graph theory, and the relative background of our research and main works on symmetry and fault-tolerant analysis of graphs.Chapter 2 investigates regular covers of connected pentavalent symmetric graphs of order twice a prime. A regular cover of a connected graph is called cyclic or dihe-dral if its transformation group is cyclic or dihedral respectively, and arc-transitive (or symmetric) if the fibre-preserving automorphism subgroup acts arc-transitively on the regular cover. In this chapter, we give a full classification of arc-transitive cyclic and dihedral covers of a connected pentavalent symmetric graph of order twice a prime. All those covers are explicitly constructed as Cayley graphs on some groups, and their full automorphism groups are determined.Chapter 3 focuses on connected pentavalent symmetric graphs of order a small number times a prime power. A connected symmetric graph of prime valency is basic if its automorphism group contains no nontrivial normal subgroup having more than two orbits. Let p be a prime.Firstly, we classify the connected pentavalent symmetric graphs of order 2p3 com-pletely. All those symmetric graphs are appeared as normal Cayley graphs on some groups of order 2p3 and their automorphism groups are determined. For p=3, no connected pentavalent symmetric graphs of order 2p3 exist. However, for p=2 or 5, such symmetric graph exists uniquely in each case. For p≥7, the connected pentava-lent symmetric graphs of order 2p3 consist of seven infinite families; six of them are 1-regular and exist if and only if 5| (p-1), while the other one is 1-transitive but not 1-regular and exists if and only if 5| (p ± 1).Secondly, we determined all the connected pentavalent basic graphs of order Ap" or 6p", where n is a non-negative integer. It is shown that, up to isomorphism, there exist only two pentavalent symmetric basic graphs of order 4p" with order 16 or 36 and five such graphs of order 6p" with order 6,42,66,114 or 162. As an application, connected pentavalent symmetric graphs of order 4p1,4p3 or 6p2 are classified. Con-nected pentavalent symmetric graphs of order 4p or 6p have been classified in [Discrete Mathematics,2011 (311):2259-2267].Chapter 4 gives a depiction of connected pentavalent symmetric graphs of square-free order. Consequently, a complete classification of connected symmetric graphs of order 2pqr is obtained, where r< q< p are three odd primes.Chapter 5 investigates fault-tolerant analysis of n-dimensional hypercubes Qn and n-dimensional balanced hypercubes BHn.We first analyze fault-tolerance of hypercubes in terms of fault-tolerant cycle em-bedding. Let F be the faulty set of a graph Qn and let fv, fe be the numbers of faulty vertices and faulty edges in F, respectively. An edge e is said to be free if e and its end-vertices are not in F, and a cycle is said to be fault-free if it has no vertices or edges contained in F. In this chapter, we prove that each free edge in a Qn for n≥3 lies on a fault-free cycle of any even length from 6 to 2n-2fv if fv+fe≤2n-5,fe≤ n-2 and each fault-free vertex is incident to at least two free edges. This result confirms a conjecture proposed by Tsai in [Information Processing Letters,2007 (102):242-246].Finally, we analyze fault-tolerance of balanced hypercubes in terms of extra con-nectivity. Given a connected graph Γ and a non-negative integer h, the h-extra con-nectivity Kh(Γ) of Γ is the minimum cardinality of a set of vertices in Γ, if it exists, whose deletion disconnects Γ and leaves each remaining component with at least h+1 vertices. For an n-dimensional balanced hypercube BHn with n≥ 2, we show that K2(BHn)= K3(BHn)= 4n-4 and K4(BHn)= K5(BHn)= 6n-8. An upper bound for the h-extra connectivity of balanced hypercubes for every integer h≤2n-1 is also obtained. This result improves a result given by Yang in [Applied Mathematics and Computation,2012 (219):970-975], where K1(BHn)= 4n-4 was proved.In Chapter 6, we discuss some problems to be solved.