Mutually Independent Hamiltonianicity of Pancake Graphs and Star Graphs
Cheng‐Kuan Lin, Jimmy J.M. Tan, Hua‐Min Huang, D. Frank Hsu, Lih‐Hsing Hsu · Proceedings of the ... International Symposium on Parallel Architectures, Algorithms, and Networks (ISPAN) · 2008
A hamiltonian cycle C of a graph G is described as langu1, u2,..., un(G), u1rang to emphasize the order of vertices in C. Thus, u1is the start vertex and uiis the i-th vertex in C. Two hamiltonian cycles of G start at a vertex x, C1= langu1, u2,..., un(G), u1rang and C2= langv1, v2,..., vn(G), v1rang, are independent if x = u1= v1and u1ne vifor every i, 2 les i les n(G). A set of hamiltonian cycles {C1, C2,..., Ck} of G are mutually independent if any two different hamiltonian cycles are independent. The mutually independent hamiltonicity of graph G, IHC(G), is the maximum integer k such that for any vertex u of G there exist k-mutually independent hamiltonian cycles ofG starting at u. Inthispaper, we are going to study IHC(G) for the n-dimensional pancake graph Pnand the n-dimensional star graph Sn. We prove that IHC(Pn) = n - 1 if n ges 4 and IHC(Sn) = n-1 if nges5.