FAULT-TOLERANT HAMILTONIAN LACEABILITY AND FAULT-TOLERANT CONDITIONAL HAMILTONIAN FOR BIPARTITE HYPERCUBE-LIKE NETWORKS
Abstract
A bipartite graph G is hamiltonian laceable if there is a hamiltonian path between any two vertices of G from distinct vertex bipartite sets. A bipartite graph G is k-edge fault-tolerant hamiltonian laceable if G - F is hamiltonian laceable for every F ⊆ E(G) with |F| ≤ k. A graph G is k-edge fault-tolerant conditional hamiltonian if G - F is hamiltonian for every F ⊆ E(G) with |F| ≤ k and δ(G - F) ≥ 2. Let G0 = (V0, E0) and G1 = (V1, E1) be two disjoint graphs with |V0| = |V1|. Let Er = {(v,ɸ(v)) | v ϵ V0,ɸ(v) ϵ V1, and ɸ: V0 → V1 is a bijection}. Let G = G0 ⊕ G1 = (V0 ⋃ V1, E0 ⋃ E1 ⋃ Er). The set of n-dimensional hypercube-like graphHn is defined recursively as (a) H1 = K2, K2 is the complete graph with two vertices, and (b) if G0 and G1 are in Hn, then G = G0 ⊕ G1 is in Hn+1. Let Bn be the set of graphs G where G is bipartite and G ϵ Hn. In this paper, we show that every graph in Bn is (n - 2)-edge fault-tolerant hamiltonian laceable if n ≥ 2 and every graph in Bn is (2n - 5)-edge fault-tolerant conditional hamiltonian if n ≥ 3.
