betaFeedback

WorksMathematics

An extremal question of Erdős et al. on cycles

Abstract

This paper addresses an extremal problem on long cycles proposed by Erdős, Faudree, Schelp and Simonovits in 1989. Let 2≤k≤d<n2\le k\le d<n be positive integers. For an n-vertex simple graph G, let θ+Gθ_+^G count vertices of degree at least d, and C≥k+1C_{\ge k+1} denote a cycle of length at least k+1k+1. The original conjecture claimed that G contains a C≥k+1C_{\ge k+1} whenever θ+G≥⌊k/2⌋⌊(n−1)/d⌋+2θ_+^G \ge \lfloor k/2 \rfloor \lfloor (n-1)/d \rfloor+2. Li, Ma and Ning disproved it with infinite counterexamples and gave linear lower bounds. Gan, Yi and Jiang later obtained piecewise sufficient conditions depending on the parity of k, whose bounds are sharp only when k=dk=d and loose for k≠dk\ne d. We derive a new sufficient condition for C≥k+1C_{\ge k+1}. For odd k=dk=d, we use Woodall's sharp bound θ+G≥k(n−2)/(2(k−1))+1θ_+^G \ge k(n-2)/(2(k-1))+1. For all other admissible parameters, our threshold is unified and independent of the parity of k: θ+G≥⌊k/2⌋(n−1)/d+(n−d−1)⌊k/2⌋/(d(d−⌊k/2⌋))+1θ_+^G \ge \lfloor k/2 \rfloor (n-1)/d + (n-d-1)\lfloor k/2 \rfloor/(d(d-\lfloor k/2 \rfloor))+1. We construct C≥k+1C_{\ge k+1}-free graphs to prove tightness for all admissible k. This resolves this long-standing Erdős-type extremal problem concerning high-degree vertices and long cycles.

Paper details

vlnc:W_rqqc2bgh
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 4

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…