Extremal problems of Erdős, Faudree, Schelp and Simonovits on paths and cycles

Abstract

For positive integers $n>d\ge k$, let $\ddot{I}•(n,d,k)$ denote the least integer $\ddot{I}•$ such that every $n$-vertex graph with at least $\ddot{I}•$ vertices of degree at least $d$ contains a path on $k+1$ vertices. Many years ago, Erdős, Faudree, Schelp and Simonovits proposed the study of the function $\ddot{I}•(n,d,k)$, and conjectured that for any positive integers $n>d\ge k$, it holds that $\ddot{I}•(n,d,k)\le \lfloor \frac{k-1}{2}\rfloor \lfloor \frac{n}{d+1}\rfloor +\hat{I}\mu$, where $\hat{I}\mu =1$ if $k$ is odd and $\hat{I}\mu =2$ otherwise. In this paper we determine the values of the function $\ddot{I}•(n,d,k)$ exactly. This confirms the above conjecture of Erdős et al. for all positive integers $k\ne 4$ and in a corrected form for the case $k=4$. Our proof utilizes, among others, a lemma of Erdős et al. \cite{EFSS89}, a theorem of Jackson \cite{J81}, and a (slight) extension of a very recent theorem of Kostochka, Luo and Zirlin \cite{KLZ}, where the latter two results concern maximum cycles in bipartite graphs. Moreover, we construct examples to provide answers to two closely related questions raised by Erdős et al.

13 pages