Mutually Independent Hamiltonianicity of Pancake Graphs and Star Graphs

A hamiltonian cycle C of a graph G is described as langu₁, u₂,..., u_n(G), u₁rang to emphasize the order of vertices in C. Thus, u₁ is the start vertex and u_i is the i-th vertex in C. Two hamiltonian cycles of G start at a vertex x, C₁ = langu₁, u₂,..., u_n(G), u₁rang and C₂ = langv₁, v₂,..., v_n(G), v₁rang, are independent if x = u₁ = v₁ and u₁ ne v_i for every i, 2 les i les n(G). A set of hamiltonian cycles {C₁, C₂,..., C_k} 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 P_n and the n-dimensional star graph S_n. We prove that IHC(P_n) = n - 1 if n ges 4 and IHC(S_n) = n-1 if nges5.