On Fault Tolerant Hamiltonicity Of Several Classes Of Interconnection Networks

It is quite natural that an interconnection network may be modeled by a simple graph whose vertices represent components of the network and whose edges represent physical communica-tion links. Such a graph is called the topological structure of the interconnection network. Graph theory is a fundamental and powerful mathematical tool for designing and analyzing interconnection networks, since the topological structure of an interconnection network is a graph.One of the essential issues in evaluating an interconnection network is to study how well other existing networks call be embedded into this network. Cycle-embedding is a central issue because networks with cycle topology are suitable for designing simple algorithms with low communication costs. Also the research of cycle-embedding in networks can be viewed as an extension of theoretical research on hamiltonicity.In a network since vertex or edge failures may occur, it is significantly meaningful to consider fault tolerance of the network. In designing or selecting a topological structure of a interconnection network, one fundamental consideration is the fault tolerance.The alternating group graph was proposed as an interconnection network topology for computing systems. It has many advantages over n-cubes and star graphs. Being having the two major principle-high performance and lower cost it has been intensively studied. We study the fault tolerant cycle embedding problem, the maximum-edge connectivity and the designing of a network. The main works and contributions of this dissertation are as follows:(1) We study the fault-tolerant hamiltonicity and fault-tolerant hamiltonian connectivity of an n-dimensional alternating group graph AGn. We give an optimal result for every n≥4:AGn is (2n-6)-fault-tolerant hamiltonian and (2n-6)-fault-tolerant pancyclic. Also it is (2n-7)-fault-tolerant hamiltonian-connected. The result we obtained is optimal on the degree of AGn. It is an improvement of a previous result given by J.-M. Chang.(2) We define a matching composition network G=G(V1∪V2,E1∪E2∪M), in which M is a perfect matching between V1 and V2. The upper and lower bounds of the diameter of G are given. The relationship between some parameter of G and the two components is studied. Also, the pancyclicity and panconnectivity of them are analyzed.(3) Using the properties of a convex function and numerical theory we study the inverse degree of a connected graph. Conditions for a class of graphs to be maximally edge-connected are given. Examples show the obtained result is effective.(4) Line graphical method, cartesian product method and algebraic method are the three usually used methods to design a network. By the third method we construct a class of graphs associated to each partially ordered set P and show that if the chromatic numberχ(G(P)) and the clique numberω(G(P)) are finite, thenχ(G(P))=ω(G(P))= n+1 in which n is the number of minimal prime ideals of P.