Mutually independent hamiltonian paths in star networks
Cheng‐Kuan Lin, Hua‐Min Huang, Lih‐Hsing Hsu, Sheng Bau · Networks · 2005
Two hamiltonian paths P1 = 〈u1, u2,…,un(G)〉 and P2 = 〈v1, v2,…,vn(G)〉 of G from u to v are independent if u = u1 = v1, v = vn(G) = un(G), and vi ≠ ui for every 1 < i < n(G). A set of hamiltonian paths, lP1, P2,…,Pkr, of G from u to v are mutually independent if any two different hamiltonian paths are independent from u to v. 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 exists k-mutually independent hamiltonian paths between any two nodes from distinct partite sets. The mutually independent hamiltonian laceability of a bipartite graph G, IHPL(G), is the maximum integer k such that G is k-mutually independent hamiltonian laceable. Let Sn denote the n-dimensional star graph. We prove that IHPL(S2) = 1, IHPL(S3) = 0, and IHPL(Sn) = n- 2 if n ≥ 4. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 46(2), 110–117 2005