Minimum multiplicities of subgraphs and Hamiltonian cycles (Q1849906)

If \(G\) is a finite simple graph and \(U\) is a spanning subgraph of \(G\), then there are at least \({|A(G)|} \over {|A(U) \cap A(G)|}\) distinct subgraphs of \(G\) which are isomorphic to \(U\) (here, \(A(G)\) denotes the automorphism group of \(G\)). \(U\) is called a fixing subgraph if there are exactly this number of subgraphs of \(G\) which are isomorphic to \(U\), and a strong fixing subgraph if, in addition, \(A(U) \subseteq A(G)\) (that is, each automorphism of \(U\) extends to an automorphism of \(G\)). The author proves that each Hamiltonian cycle of \(G\) is a strong fixing subgraph of \(G\) if and only if \(G\) is one of \(C_n\), \(K_n\) or \(K_{n,n}\). He also studies the question of which generalized Petersen graphs \(G(n,k)\) have the property that each Hamiltonian cycle is a fixing subgraph (the generalized Petersen graph \(G(n,k)\), \(1 \leq k \leq n/2\), has vertices \(a_1, \ldots, a_n, b_1, \ldots, b_n\), and edges \(a_ia_{i+1}\), \(a_ib_i\) and \(b_ib_{i+k}\) for each \(i\), where all indices are understood mod\ \(n\)).