The number of cycle lengths in graphs of given minimum degree and girth (Q1301632)

Let \(n(g,k)\) be the minimum number of different cycle lengths in a graph of given minimum degree \(k\) and girth \(g\). The paper gives lower bounds for \(n(g,k)\). The most general lower bound is \(ck^{g/8}\). For particular values of \(g\) better lower bounds are given: \(n(5,k)\geq (k^2+ k-2)/4\), \(n(9,k)\geq c_1k^3\), \(n(7,k)\geq c_2 k^{5/2}\), and for \(t\geq 2\), \(n(4t- 1,k)\geq c_3 k^{t/2}\). The lower bound for \(n(5,k)\) is the best possible within a constant multiplicative factor, the other lower bounds are likely far from the truth.