Maximizing hamiltonian pairs and k-sets via numerous leaves in a tree

AbstractSharp exponential upper bound, k!n−1, on the number of hamiltonian k-sets (i.e., decompositions into k hamiltonian cycles) among multigraphs G is found if the number, n, of vertices is fixed, n≥3. Moreover, the upper bound is attained iff G=Cnk where Cnk is the k-fold n-cycle Cn. Furthermore, if G≠Cnk then the number of hamiltonian k-sets in G is less than or equal to k!n−1/k, the bound, if k≥2, being attained for exactly ⌊n−22⌋ nonisomorphic 2k-valent multigraphs G of order n≥4. For k≥2, the number of hamiltonian k-sets among multigraphs of order at least 3 is even