Long cycles in graphs with no subgraphs of minimal degree 3 (Q1122589)

A graph G of order n is said to be degree k-critical if it has exactly \(n(k-1)-\binom{k}{2}+1\) edges and no proper subgraph of minimal degree k. Define \(f_ k(n)\) to be the minimum, over all degree k-critical graphs of order n, of the length of the longest cycle. \textit{P. Erdős, R. Faudree, A. Gyárfás} and \textit{R. H. Schelp} proved that \(\lfloor \log_ 2n\rfloor \leq f_ 3(n)\leq cn^{1/2}\) for some constant c. [Ars Comb. 25B, 195-201 (1988; Zbl 0657.05048)]. The authors prove that \(f_ 3(n)=4 \log_ 2n+O(\log_ 2\log_ 2n).\) Identical techniques can be extended to the case of general k.