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 |
| |
Affiliation: | (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: | KeywordHeading" >AMS Subject Classification 05C45 05C38 |
本文献已被 SpringerLink 等数据库收录! |
|