<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 1" %>
Mutually Independent Hamiltonian Connectivity of (n,k)-Star Graphs
Selina Yo-Ping Chang1, Justie Su-Tzu Juan1, Cheng-Kuan Lin2, Jimmy J. M. Tan2, and Lih-Hsing Hsu3
1Department of Computer Science and Information Engineering, National Chi Nan University, Nantou 54561, Taiwan
2Department of Computer Science, National Chiao Tung University, Hsinchu 30010, Taiwan
3Department of Computer Science and Information Engineering, Providence University, Taichung 43301, Taiwan
Annals of Combinatorics 13 (1) pp.27-52 March, 2009
AMS Subject Classification: 05C45, 05C38
A graph $G$ is hamiltonian connected if there exists a hamiltonian path joining any two distinct nodes of $G$. Two hamiltonian paths $P_1 = \big\langle u_1,\, u_2, \ldots,\, u_{\nu(G)} \big\rangle$ and $P_2 = \big\langle v_1,\, v_2, \ldots,\, v_{\nu(G)} \big\rangle$ of $G$ from $u$ to $v$ are independent if $u = u_1 = v_1$, $v = u_{\nu(G)} = v_{\nu(G)}$, and $u_i \ne v_i$ for every $1 < i < \nu(G)$. A set of hamiltonian paths, $\{ P_1,\, P_2, \ldots,\, 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 \ge 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$.
Keywords: hamiltonian, hamiltonian connected, (n,k)-star graphs


1. S.B. Akers and B. Krishnamurthy, A group-theoretic model for symmetric interconnection networks, IEEE Trans. Comput. 38 (4) (1989) 555-–566.

2. J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, Elsevier Publishing Co., New York, 1976.

3. J.-H. Chang and J. Kim, Ring embedding in faulty (n; k)-star graphs, In: Proceedings of the Eighth International Conference on Parallel and Distributed Systems (ICPADS 2001), IEEE Computer Society, Washington, (2001) pp. 99-–106.

4. W.-K. Chiang and R.-J. Chen, The (n; k)-star graph: a generalized star graph, Inform. Process. Lett. 56 (5) (1995) 259-–264.

5. S.-Y. Hsieh, G.-H. Chen, and C.-W. Ho, Hamiltonian-laceability of star graphs, Networks 36 (4) (2000) 225–-232.

6. H.-C. Hsu, Y.-L. Hsieh, J.J.M. Tan, and L.-H. Hsu, Fault hamiltonicity and fault hamiltonian connectivity of the (n; k)-star graphs, Networks 42 (4) (2003) 189-–201.

7. J.-S. Jwo, S. Lakshmivarahan, and S.K. Dhall, Embedding of cycles and grids in star graphs, J. Circuits Systems Comput. 1 (1) (1991) 43-–74.

8. F.T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes, Morgan Kaufmann, San Mateo, CA, 1992.

9. T.-C. Lin, D.-R. Duh, and H.-C. Cheng,Wide diameters of (n; k)-star networks, In: Proceedings of the International Conference on Computing, Communications, and Control Technologies (CCCT'04), Austin, Texas, (2004) pp. 160-–165.

10. C.-K. Lin, H.-M. Huang, L.-H. Hsu, and S. Bau, Mutually independent hamiltonian paths in star networks, Networks 46 (2) (2005) 110-–117.

11. Y. Saad and M.H. Schultz, Topological properties of hypercubes, IEEE Trans. Comput. 37 (7) (1988) 867-–872.

12. C.-M. Sun, C.-K. Lin, H.-M. Huang, and L.-H. Hsu, Mutually independent hamiltonian paths and cycles in hypercubes, J. Interconnection Networks 7 (2) (2006) 235-–255.

13. Y.-H. Teng, J.J.M. Tan, T.-Y. Ho, and L.-H. Hsu, On mutually independent hamiltonian paths, Appl. Math. Lett. 19 (4) (2006) 345–-350.