Studies On Network And Combinatorial Properties Of Some Classes Of Cayley Graphs

With continuous development of information technology,data scale and computation quantity increase as well,so there are urgent needs of high-speed and betterperformance computer systems.However,when semiconductor manufacturing level jumps from 10 nm to 7nm level,the designers will face challenges such as quantum tunneling effect,power consumption,heat radiation,design closure and cost,therefore,it is hard to promote performance of a single processor.Multi-core parallel and distributed systems emerged and were extensively developed and investigated.The fundamental character of the interconnection network is that processors and memories are connected with physical links according to given topology,making information transmission and processing between a host of processors,which will promote its ability of computation.As the advances of performance of computer systems,the overall scale is also expanding.China's Tianhe-2 supercomputer has a floating-point speed of 339 million billion per second,which uses 16000 nodes,3.12 million processors in all.When such a large system putting into use,failure of processors or links is inevitable.From the robustness of systems point of view,we hope that if failure happens to a single unit,the system,as an integral,can function without collapse,in other words,the system should have the capability of fault tolerance.Fault tolerance is a key index to measure performance of the interconnection networks,which mainly considers that the retention ability of particular properties in faulty networks.Therefore,fault-tolerance is an important issue in parallel systems.Multi-processor parallel system,distributed system consist of large quantities of functional components,which will cause failure of elements or links between elements.The link model of units in the system is called topology of the network model.Interconnection networks can be modeled by graphs,where vertices represent elements and edges represent physical links between elements,additionally,incidence function designate link type of the elements,utilizing to deploy data transmission and exchanging of the system.Interconnection networks we consider in this thesis possess the following properties: high symmetry(the corresponding graph is highly symmetric),which can distribute information uniformly,yielding efficient routing algorithm;excellent fault-tolerance,if failure occurs in few nodes or links(vertices or edges failure of the corresponding graph),the system can keep original structure properties.In topological structure sense,the network model of a system reveals its structure properties.On the other hand,graphs can be used to depict topology structure of interconnection networks.In this thesis,we will use “graph” and “interconnection network” interchangeably.Cayley graph is a class of high symmetry and regularity graphs,that is why Cayley graphs are usually applied in network topology designing.Accordingly,various famous network topologies are proved to be Cayley graphs,for example,balanced hypercubes,cube-connected cycles.However,only few studies on fault-tolerance of the balanced hypercube has yet known.This thesis mainly studies fault-tolerance and symmetric properties of some Cayley graphs,particularly,balanced hypercubes,honeycomb toroidal graphs.Finally,we extend our research objects to fault-tolerance,reliability and embeddability of semi-Cayley graphs and Bi-Cayley graphs,which possess several similar properties of Cayley graphs.The research on the above field has achieved the following results.(1)Fault tolerance and stability of interconnection networks are two crucial factors,so it is important to consider fault tolerance of the balanced hypercube.The balanced hypercube is a variant of the hypercube,and its key property is that there exists a fault-free Hamiltonian path.A Hamiltonian path of a graph is a path that traverses all its vertices.A graph is called Hamiltonian connected if there exists a Hamiltonian path between any two vertices.We prove that the balanced hypercube is 29)-2 edge fault-tolerant Hamiltonian laceable.(2)In an application of large systems,failure is inevitable,so it is meaningful to consider faulty elements in networks.Fault tolerant cycle embedding(or path embedding)is to find fault-free a cycle(or a path)in a faulty interconnection network.Under this assumption,it is meaningful to find a cycle or path travels given vertices or edges.The problem of traversing a given set of edges has already studied in the hypercube and its variants,however,only edge bipancyclicity of the balanced hypercube is known.In chapter three of this thesis,we study Hamiltonian laceability of balanced hypercube passing through an edge,and obtain the following result:for an arbitrary edge 0),there exists a Hamiltonian path between two vertices in different partite sets passing through 0).(3)The forwarding index was introduced for measuring efficiency and capacity of networks.Honeycomb toroidal graph was proposed as a class of novel interconnection networks.Calculating the forwarding index relies on computing sums of distance of any two distinct vertices,which is exact two times of the Wiener index of the graph.For honeycomb toroidal graphs satisfying (,2,2 + mod(2)),when 8)? ? 29)-8)and 9)? 28)+ 1,the Wiener index is known.For honeycomb toroidal graphs dissatisfying the above condition is not clear.In chapter four of this thesis,a linear-time algorithm is given to compute the Wiener index and forwarding index of almost all honeycomb toroidal graphs.(4)Cayley graphs have numerous desirable properties,such as simple,high symmetry,easy scalability and etc.,gradually becoming a powerful tool for constructing and designing interconnection networks.The properties above can maximally simplify topology maintenance and routing algorithm designing,therefore,many interconnection network topologies are based on Cayley graph model in group theory.Therefore,in chapter five,we discuss applications of different Cayley graphs in interconnection networks,and in detail,illustrate algebraic and combinatorial properties of Cayley graphs such as symmetry and fault tolerance.This thesis mainly study on fault tolerance and other combinatorial properties of several Cayley graphs(including the balanced hypercube,honeycomb toroidal graphs and Cayley graphs constructed from complete simple group),laying the foundation for applications of interconnection network design.