Mutually Independent Hamiltonian Connectivity of (n, k)-Star Graphs

Abstract

A graph G is hamiltonian connected if there exists a hamiltonian path joining any two distinct nodes of G. Two hamiltonian paths P(1) = < u(1), u(2),..., u(v(G))> and P(2) = < v(1), v(2),...,v(v(G))> of G from u to v are independent if u = u(1) = v(1), v = u(v(G)) = v.( G), and u(i) not equal v(i) for every 1 < i < v(G). A set of hamiltonian paths, {P(1), P(2),..., P(k)}, of G from u to v are mutually independent if any two different hamiltonian paths are independent from u to v. A graph is k mutually independent hamiltonian connected if for any two distinct nodes u and v, there are k mutually independent hamiltonian paths from u to v. The mutually independent hamiltonian connectivity of a graph G, IHP( G), is the maximum integer k such that G is k mutually independent hamiltonian connected. Let n and k be any two distinct positive integers with n-k >= 2. We use S(n,k) to denote the (n, k)-star graph. In this paper, we prove that IHP(S(n,k)) = n-2 except for S(4,2) such that IHP(S(4,2)) - 1.