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

Selina Yo-Ping Chang^{1}, Justie Su-Tzu
Juan^{1}, Cheng-Kuan
Lin^{2}, Jimmy J. M.
Tan^{2}, and Lih-Hsing
Hsu^{3}
^{1}Department of Computer
Science and Information Engineering, National Chi Nan
University, Nantou 54561, Taiwan

^{2}Department of Computer
Science, National Chiao Tung University, Hsinchu 30010,
Taiwan

^{3}Department of Computer
Science and Information Engineering, Providence
University,
Taichung 43301, Taiwan
**AMS Subject Classification: **05C45, 05C38
**Keywords: **hamiltonian, hamiltonian connected, (n,k)-star
graphs

lhhsu@pu.edu.tw

Annals of Combinatorics 13 (1) pp.27-52 March, 2009

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 = \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$.
References:

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.