| Popis: |
A hamiltonian cycle C of a graph G is an ordered set 〈u1,u2,…,un(G),u1〉 of vertices such that ui≠uj for i≠j and ui is adjacent to ui+1 for every i∈{1,2,…,n(G)−1} and un(G) is adjacent to u1, where n(G) is the order of G. The vertex u1 is the starting vertex and ui is the ith vertex of C. Two hamiltonian cycles C1=〈u1,u2,…,un(G),u1〉 and C2=〈v1,v2,…,vn(G),v1〉 of G are independent if u1=v1 and ui≠vi for every i∈{2,3,…,n(G)}. A set of hamiltonian cycles {C1,C2,…,Ck} of G is mutually independent if its elements are pairwise independent. The mutually independent hamiltonicity IHC(G) of a graph G is the maximum integer k such that for any vertex u of G there exist k mutually independent hamiltonian cycles of G starting at u.In this paper, the mutually independent hamiltonicity is considered for two families of Cayley graphs, the n-dimensional pancake graphs Pn and the n-dimensional star graphs Sn. It is proven that IHC(P3)=1, IHC(Pn)=n−1 if n≥4, IHC(Sn)=n−2 if n∈{3,4} and IHC(Sn)=n−1 if n≥5. |
Full Text from ScienceDirect