FAULT-TOLERANT HAMILTONIAN LACEABILITY AND FAULT-TOLERANT CONDITIONAL HAMILTONIAN FOR BIPARTITE HYPERCUBE-LIKE NETWORKS

摘要

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 is contained in E(G) with |F| ≤ k. A graph G is k-edge fault-tolerant conditional hamiltonian if G - F is hamiltonian for every F is contained in E(G) with |F| ≤ k and δ(G - F) ≥ 2. Let G_0 = (V_0, E_0) and G_1 = (V_1,E_1) be two disjoint graphs with |V_0| = |V_1|. Let E_r = {(v,ø>(v)) | v ∈ V_0,ø(v) ∈ V_1, and ø : V_0 → V_1 is a bijection}. Let G = G_0 ⊕ G_1 = (V_0 U V_1,E_0 U E_1 U E_r). The set of n-dimensional hypercube-like graph H_n is defined recursively as (a) H_1 = K_2, K_2 is the complete graph with two vertices, and (b) if G_0 and G_1 are in H_n, then G = G_0 ⊕ G_1 is in H_(n+1). Let B_n be the set of graphs G where G is bipartite and G ∈H_n. In this paper, we show that every graph in B_n is (n - 2)-edge fault-tolerant hamiltonian laceable if n ≥ 2 and every graph in B_n is (2n - 5)-edge fault-tolerant conditional hamiltonian if n ≥ 3.