首页|Extremal problems of Erdos, Faudree, Schelp and Simonovits on paths and cycles
Extremal problems of Erdos, Faudree, Schelp and Simonovits on paths and cycles
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NSTL
Elsevier
For positive integers n > d >= k, let phi( n, d, k) denote the least integer phi such that every n-vertex graph with at least phi vertices of degree at least d contains a path on k + 1 vertices. Many years ago, Erdos, Faudree, Schelp and Simonovits proposed the study of the function phi(n, d, k), and conjectured that for any positive integers n > d >= k, it holds that phi(n, d, k) <= right perpendiculark-1/2left perpendicular right perpendicularn/d+1left perpendicular + epsilon, where epsilon = 1 if k is odd and epsilon = 2 otherwise. In this paper we determine the values of the function phi( n, d, k) exactly. This confirms the above conjecture of Erdos et al. for all positive integers k not equal 4 and in a corrected form for the case k = 4. Our proof utilizes, among others, a lemma of Erdos et al. [3], a theorem of Jackson [6], and a (slight) extension of a very recent theorem of Kostochka, Luo and Zirlin [7], 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 Erdos et al. (C) 2021 Elsevier Inc. All rights reserved.
NSTL
Elsevier
