Improved bound on the number of cycle sets

2025/01/17 by Nenadov, Rajko
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2501.09904

Abstract

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.

Related

• On the Number of Cycles in a Graph
• On the number of cycles in a graph with restricted cycle lengths
• A note on the number of edges in a Hamiltonian graph with no repeated cycle length
• Cycles with many chords
• Bounding the number of cycles in a graph in terms of its degree sequence