betaFeedback

WorksMathematics

Minimum degree thresholds for even cycle residues

Abstract

Dean's conjecture asserts that, for every integer m≥3m\ge3, every graph of minimum degree at least mm has a cycle whose length is divisible by mm. This degree bound is best possible for odd mm. For every integer k≥2k\ge2, we prove that every graph of minimum degree at least 2k−12k-1 has a cycle whose length is congruent to rr modulo 2k2k for every even r≢2(mod2k)r\not\equiv2\pmod{2k}. Consequently, 2k−12k-1 is the sharp minimum degree threshold for a cycle whose length is divisible by 2k2k. For bipartite graphs, we prove that minimum degree at least kk guarantees the same residue classes for every k≥4k\ge4, and we characterize their end-blocks when no cycle has length congruent to 22 modulo 2k2k. The bipartite degree bound is also sharp, and the exclusion of residue 22 is necessary even for connected graphs of arbitrarily large order.

Paper details

vlnc:W_fmdcbd9x
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC-BY-NC-ND-4.0
Usage

views · 0

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…