Combinatorial Theory

The cycle set of a graph \(G\) is the set consisting of all sizes of cycles in \(G\). Answering a conjecture of Erdős and Faudree, Verstraëte showed that there are at most \(2^{n - n^{1/10}}\) different cycle sets of graphs with \(n\) vertices. We improve this bound to \(2^{n - n^{1/2 - o(1)}}\). Our proof follows the general strategy of Verstraëte of reducing the problem to counting cycle sets of Hamiltonian graphs with many chords or a large maximum degree. The key new ingredients are near-optimal container lemmata for cycle sets of such graphs.

Mathematics Subject Classifications: 05C30, 05C38

Keywords: Cycle sets, container method