Hamiltonicity In K-ary N-cube With Faulty Edges

Interconnection network is a connection between processors in a large-scale computer system,which can be represented by an undirected connection graph.Vertices in the graph represent processors in the system,and edges represent the lines between processors in the system.Due to its excellent topological properties,such as easy implementation and low latency,k-ary n-cube network has become one of the most important interconnection networks.In the study of interconnection network,it is very important to study whether the network has Hamiltonicity and no traffic coverage.With the continuous expansion of the scale of multi-processor system,the possibility of failure of the processor and the circuit between the processor is increasing.Therefore,it is very necessary to study the Hamiltonicity of the network with fault elements.Generally speaking,the more the number of fault elements allowed to occur,the better the fault tolerance of the network under the condition of maintaining Hamiltonicity.At present,many scholars have discussed the fault point and fault edge under different conditions and obtained some research results in the study of Hamiltonianism of k-ary n-cube.In this thesis,we continue to study the Hamiltonicity of a k-ary n-cube network with fault elements,and further explore the upper bound of the number of fault elements allowed to occur in the network under the premise that the network remains Hamiltonicity.In this thesis,Hamiltonian properties of k-ary 4-cube networks are studied firstly.Firstly,the existence of Hamilton path and two non-intersection path covering the vertex generating subgraph of the partial-molecular cube of k-ary 4-cube is discussed.Based on this,we continue to study the Hamiltonian properties of k-ary n-cube networks,where n?3.The existence of Hamilton path and two non-intersection path covering the vertex generating subgraph of the partial-molecular cube of k-ary n-cube is discussed.Based on this,the following conclusions are proved:Theorem 1:Let F be a set of faulty edges in Q4k with k?4.k is even,|F|?13 and the degree of every vertex in Q4k-F is at least 3.If k subcubes Q[i](i=0,1,…,k-1)obtained by dividing Q4k along any dimension satisfies the degree of every vertex in Q[i]-Fi is at least 2,then there is a Hamilton path between any two points in Q4k-F,where Fi is the set of fault edges in Q[i].Theorem 2:Let F be a set of faulty edges in Qnk with k?4,k is even and |F|? 6n-11.There still exists a Hamiltonian cycle in Qnk-F if the degree of every vertex in Qnk-F is at least 3.