Construction Schemes for Edge Fault-Tolerance of Ring Networks

摘要

The k-edges fault-tolerance-Hamiltonian graphs have been studied by many researchers. In this paper, we introduce the 2-path-required Hamiltonian graphs. We will show that the complete bipartite graph K_(n,n) is(n - 3)-edges fault-tolerance 2-path-required Hamiltonian graphs. We also prove the relationship between hyper-Hamiltonian laceability and 2-path-required Hamiltonian property. Moreover, we present the construction scheme for 2-path-required Hamiltonian graphs, named vertex join. Applying this scheme, we can construct many new 2-path-required Hamiltonian graphs with edges fault-tolerant property.