Mutually independent hamiltonian cycles for the pancake graphs and the star graphs

A hamiltonian cycle  CC of a graph GG is an ordered set 〈u1,u2,…,un(G),u1〉〈u1,u2,…,un(G),u1〉 of vertices such that ui≠ujui≠uj for i≠ji≠j and uiui is adjacent to ui+1ui+1 for every i∈{1,2,…,n(G)−1}i∈{1,2,…,n(G)−1} and un(G)un(G) is adjacent to u1u1, where n(G)n(G) is the order of GG. The vertex u1u1 is the starting vertex and uiui is the iith vertex of CC. Two hamiltonian cycles C1=〈u1,u2,…,un(G),u1〉C1=〈u1,u2,…,un(G),u1〉 and C2=〈v1,v2,…,vn(G),v1〉C2=〈v1,v2,…,vn(G),v1〉 of GG are independent   if u1=v1u1=v1 and ui≠viui≠vi for every i∈{2,3,…,n(G)}i∈{2,3,…,n(G)}. A set of hamiltonian cycles {C1,C2,…,Ck}{C1,C2,…,Ck} of GG is mutually independent if its elements are pairwise independent. The mutually independent hamiltonicity   IHC(G)IHC(G) of a graph GG is the maximum integer kk such that for any vertex uu of GG there exist kk mutually independent hamiltonian cycles of GG starting at uu.In this paper, the mutually independent hamiltonicity is considered for two families of Cayley graphs, the nn-dimensional pancake graphs PnPn and the nn-dimensional star graphs SnSn. It is proven that IHC(P3)=1IHC(P3)=1, IHC(Pn)=n−1IHC(Pn)=n−1 if n≥4n≥4, IHC(Sn)=n−2IHC(Sn)=n−2 if n∈{3,4}n∈{3,4} and IHC(Sn)=n−1IHC(Sn)=n−1 if n≥5n≥5.