Fault-free Hamiltonian Cycles In Crossed Cubes With Conditional Note Faults

The hypercube network is the most famous, common and effective Internet topology nowadays. It is possessed of regularity, symmetry, strong connectivity, embedding, Hamilton, fault tolerance, what’s more, its strong recursive structure, etc. However, hypercube itself also has disadvantages that hard to be overcome, e.g., its large diameter. As an important variant of the hypercube, cross-cube has a shorter diameter and more simple recursive structure, which has aroused widespread concerns in the internation, thus, its fault tolerance also is of much concern.In order to measure the advantages and disadvantages of the network, embedding ability should be considered,for which is one of the important indicators. Therefore pancyclicity and Hamiltonian cycle embedding ability serve as standards to measure the merits and faults of the network’s structure. After being put into use, some constituent elements and lines of the networks are easy to fail, What is usually referred to is the network fault tolerance, which means the mumbers of simultaneous failures of some of the elements and (or) connection faults that the network can allow when the remaining sub-networks are still able to ensure the patency and practicality of the whole network, therefore, fault tolerance study of the network has some practical significance.Thus, the graph theory and cycle embedding in crossed cubes with conditional fault tolerance will be the main work in this article.As early as in1995, Kulasinghe P et al proved that the crossed cube CQn is not vertex-transitive for n>5. This shortcoming of the crossed cube has bring many inconvenience to the its research. Therefore, this article will provide more extensive discussion of the graph theory of the crossed cubes. We will use the relative knowledge of the group theory to divide its structure, determine the specific form of the group as well as the elements in it. This result has laid a firm foundation for the further study of high-dimensional cross-cube network and it also provides technical means and theory support for the crossed cube fault tolerance and embedding ability.In addition, based on the study of the crossed cube structural properties, we also discuss the conditional fault tolerance of hamiltonian cycle. Because of non-transitivity of the high-dimension crossed cube, it is difficult to find a non-fault Hamiltonian cycle in a fault crossed cube.On some experiences and results of previous research, using mathematical induction, we creatively put forward a new theorem and sucessfully prove it in this article. The new theorem in this paper is described below:in the situation of conditional node faults (each fault-free node is adjacent with at least two other fault-free nodes), the existence of the Hamiltonian cycles in a n-dimensional crossed cube for n≥4,even if the number of faulty nodes is up to2n-7. This result improved and perfected Hai-Liang et al.[11] research.