Mutually Independent Hamiltonian Connectivity of (n, k)-Star Graphs |
| |
| Authors: | Selina Yo-Ping Chang Justie Su-Tzu Juan Cheng-Kuan Lin Jimmy J M Tan Lih-Hsing Hsu |
| |
| Institution: | (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 |
| |
| Abstract: | A graph G is hamiltonian connected if there exists a hamiltonian path joining any two distinct nodes of G. Two hamiltonian paths  and  of G from u to v are independent if u = u
1 = v
1, v = u
v(G)
= v
v(G)
, and u
i
≠ 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.
|
| |
| Keywords: | AMS Subject Classification" target="_blank">AMS Subject Classification 05C45 05C38 |
| 本文献已被 SpringerLink 等数据库收录！ |
|
