Minimum multiplicities of subgraphs and Hamiltonian systems

Abstract

Let G be a finite simple graph with automorphism group A(G). Then a spanning subgraph U of G is a fixing subgraph of G if G contains exactly $|A(G)|/|A(G)\cap A(U)|$ subgraphs isomorphic to U: the graph G must always contain at least this number. If in addition $A(U)\subseteq A(G)$ then U is a strong fixing subgraph. Fixing subgraphs are important in many areas of graph theory. We consider them in the context of Hamiltonian graphs

arXiv commentto appear in Discrete Math