The number of sets of cycle lengths for graphs on n vertices

Sammanfattning

The cycle set C(G) of a graph G is the set of all lengths of cycles in G. Let C(n) be the number of sets C(G) arising from graphs on n vertices. Erdős and Faudree proved a lower bound of order 2^(n/2), and asked whether C(n)/2^(n/2) → ∞ and C(n)/2^n → 0. The first question remains open, while the second was answered affirmatively by Verstraëte. We present a proof due to Nenadov of the best known upper bound for C(n), improve the argument for certain classes of graphs, and study the remaining ones. In addition, we bound C(n) from below by a function more amenable to computation, which reveals numerical evidence for C(n)/2^(n/2) → ∞.