Narrow Results

Parallel paths of interconnection networks have attracted much attention in parallel computing systems, they are studied in terms of disjoint paths in an undirected graph $G$. A $k$-disjoint path cover (k-DPC for short) of a graph $G$ is a set of $k$ (internally) disjoint paths that altogether cover every vertice of the graph. A bipartite graph $H$ is one-to-one bi-k-DPC if there is a k-DPC between any pair of vertices in different partite sets. A bipartite graph is hamiltonian laceable if there exists a hamiltonian path between any pair of vertices in different partite sets. The $n$-dimensional leaf-sort graph $C{F}_n$ has many good properties, including bipartite, symmetry, vertex-transitive. In this paper, we prove that $C{F}_n$ has one-to-one bi-$(\lceil \frac{3n}{2}\rceil -2)$-DPC between any two vertices $x$ and $y$ in $C{F}_n$, where $x$, $y$ in different partite sets, and $C{F}_n$ is hamiltonian laceable.

Two hamiltonian paths P₁ = 〈v₁, v₂, …, v_n(G) 〉 and P₂ = 〈 u₁, u₂, …, u_n(G) 〉 of G are independent if v₁ = u₁, v_n(G) = u_n(G), and v_i ≠ u_i for 1 < i < n(G). A set of hamiltonian paths {P₁, P₂, …, P_k} of G are mutually independent if any two different hamiltonian paths in the set are independent. A bipartite graph G is hamiltonian laceable if there exists a hamiltonian path joining any two nodes from different partite sets. A bipartite graph is k-mutually independent hamiltonian laceable if there exist k-mutually independent hamiltonian paths between any two nodes from different partite sets. The mutually independent hamiltonian laceability of bipartite graph G, IHP_L(G), is the maximum integer k such that G is k-mutually independent hamiltonian laceable. Let Q_n be the n-dimensional hypercube. We prove that IHP_L(Q_n) = 1 if n ∈ {1,2,3}, and IHP_L(Q_n) = n - 1 if n ≥ 4. A hamiltonian cycle C of G is described as 〈 u₁, u₂, …, u_n(G), u₁ 〉 to emphasize the order of nodes in C. Thus, u₁ is the beginning node and u_i is the i-th node in C. Two hamiltonian cycles of G beginning at u, C₁ = 〈 v₁, v₂, …, v_n(G), v₁ 〉 and C₂ = 〈 u₁, u₂, …, u_n(G), u₁ 〉, are independent if u = v₁ = u₁, and v_i ≠ u_i for 1 < i ≤ n(G). A set of hamiltonian cycles {C₁, C₂, …, C_k} of G are mutually independent if any two different hamiltonian cycles are independent. The mutually independent hamiltonianicity of graph G, IHC(G), is the maximum integer k such that for any node u of G there exist k-mutually independent hamiltonian cycles of G starting at u. We prove that IHC(Q_n) = n - 1 if n ∈ {1,2,3} and IHC(Q_n) = n if n ≥ 4.

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 G₀ = (V₀, E₀) and G₁ = (V₁, E₁) be two disjoint graphs with |V₀| = |V₁|. Let E_r = {(v,ɸ(v)) | v ϵ V₀,ɸ(v) ϵ V₁, and ɸ: V₀ → V₁ is a bijection}. Let G = G₀ ⊕ G₁ = (V₀ ⋃ V₁, E₀ ⋃ E₁ ⋃ E_r). The set of n-dimensional hypercube-like graphH_n is defined recursively as (a) H₁ = K₂, K₂ is the complete graph with two vertices, and (b) if G₀ and G₁ are in H_n, then G = G₀ ⊕ G₁ 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.