1. Mutually Independent Hamiltonian Connectivity of (n, k)-Star Graphs
- Author
-
Cheng-Kuan Lin, Jiann-Mean Tan, Lih-Hsing Hsu, Justie Su-Tzu Juan, and Selina Yo-Ping Chang
- Subjects
Combinatorics ,Discrete mathematics ,symbols.namesake ,Integer ,symbols ,Discrete Mathematics and Combinatorics ,Hamiltonian (quantum mechanics) ,Hamiltonian path ,Graph ,Mathematics - Abstract
Ag raphG is hamiltonian connected if there exists a hamiltonian path joining any two distinct nodes of G. Two hamiltonian paths P1 = u1, u2 ,..., uν(G) and P2 = v1, v2 ,..., vν(G) of G from u to v are independent if u = u1 = v1, v = uν(G) = vν(G) ,a nduivi for every 1 < i < ν(G). A set of hamiltonian paths, {P1, P2 ,..., Pk} ,o fG from u to v are mutually independent if any two different hamiltonian paths are independent from u to v .A graph isk mutually independent hamiltonian connected if for any two distinct nodes u and v ,t here arek 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 inde- pendent hamiltonian connected. Let n and k be any two distinct positive integers with n−k ≥ 2. We use Sn, k to denote the (n, k)-star graph. In this paper, we prove that IHP(Sn, k )= n − 2e x- cept for S4, 2 such that IHP(S4, 2 )= 1.
- Published
- 2009