Book contents
- Frontmatter
- Contents
- Preface
- List of contributors
- Acknowlegements
- Generating expanders from two permutations
- Sum-free subsets
- Is there a different proof of the Erdős-Rado theorem?
- Almost collinear triples among N points on the plane
- Hamilton cycles in random graphs of minimal degree at least k
- The circumference of a graph with a given minimal degree
- On arithmetic progressions in sums of sets of integers
- On graphs not containing prescribed induced subgraphs
- Partitions sans petits sommants
- A compact sequential space
- The critical parameter for connectedness of some random graphs
- Multiplicative functions on arithmetic progressions: III. The large moduli
- Locally finite groups of permutations of ℕ acting on l∞
- Hypergraph games and the chromatic number
- On arithmetic graphs associated with integral domains
- On the number of certain subgraphs of graphs without large cliques and independent subsets
- Sets of multiples of Behrend sequences
- A functional equation arising from mortality tables
- The differences between consecutive primes, IV
- On the cofinality of countable products of cardinal numbers
- On σ-centered posets
- A Galvin–Hajnal conjecture on uncountably chromatic graphs
- Necessary conditions for mean convergence of Hermite–Fejér interpolation
- On the Erdős–Fuchs theorems
- A tournament which is not finitely representable
- On the volume of the spheres covered by a random walk
- Special Lucas sequences, including the Fibonacci sequence, modulo a prime
- A remark on heights of subspaces
- Incompactness for chromatic numbers of graphs
- Graphs with no unfriendly partitions
- On the greatest prime factor of an arithmetical progression
- The probabilistic lens: Sperner, Turan and Bregman revisited
- On the mean convergence of derivatives of Lagrange interpolation
- Sur une question d'Erdős et Schinzel
- Large α-preserving sets in infinite α-connected graphs
- Some recent results on interpolation
- Partitioning the quadruples of topological spaces
- Some of my favourite unsolved problems
The circumference of a graph with a given minimal degree
Published online by Cambridge University Press: 05 March 2012
- Frontmatter
- Contents
- Preface
- List of contributors
- Acknowlegements
- Generating expanders from two permutations
- Sum-free subsets
- Is there a different proof of the Erdős-Rado theorem?
- Almost collinear triples among N points on the plane
- Hamilton cycles in random graphs of minimal degree at least k
- The circumference of a graph with a given minimal degree
- On arithmetic progressions in sums of sets of integers
- On graphs not containing prescribed induced subgraphs
- Partitions sans petits sommants
- A compact sequential space
- The critical parameter for connectedness of some random graphs
- Multiplicative functions on arithmetic progressions: III. The large moduli
- Locally finite groups of permutations of ℕ acting on l∞
- Hypergraph games and the chromatic number
- On arithmetic graphs associated with integral domains
- On the number of certain subgraphs of graphs without large cliques and independent subsets
- Sets of multiples of Behrend sequences
- A functional equation arising from mortality tables
- The differences between consecutive primes, IV
- On the cofinality of countable products of cardinal numbers
- On σ-centered posets
- A Galvin–Hajnal conjecture on uncountably chromatic graphs
- Necessary conditions for mean convergence of Hermite–Fejér interpolation
- On the Erdős–Fuchs theorems
- A tournament which is not finitely representable
- On the volume of the spheres covered by a random walk
- Special Lucas sequences, including the Fibonacci sequence, modulo a prime
- A remark on heights of subspaces
- Incompactness for chromatic numbers of graphs
- Graphs with no unfriendly partitions
- On the greatest prime factor of an arithmetical progression
- The probabilistic lens: Sperner, Turan and Bregman revisited
- On the mean convergence of derivatives of Lagrange interpolation
- Sur une question d'Erdős et Schinzel
- Large α-preserving sets in infinite α-connected graphs
- Some recent results on interpolation
- Partitioning the quadruples of topological spaces
- Some of my favourite unsolved problems
Summary
Abstract
Extending a theorem of Alon, we prove a conjecture of Katchalski that every graph of order n and minimal degree at least n/k > 1 contains a cycle of length at least n/(k - 1). The result is best possible for all values of n and k (2 ≤ k < n).
Introduction
A well-known result of Erdös and Gallai [4] states that, for n ≥ k ≥ 3, a graph of order n and size greater than ½(k - 1)(n - 1) has circumference at least k, that is, it contains a cycle of length at least k. According to Dirac's [3] classical theorem, every graph of order n ≥ 3 and minimal degree at least ½n is Hamiltonian. What can one say about the circumference of a graph of order n and minimal degree at least d ≥ 2? Recently Alon [1] came close to giving a complete answer to this question when he proved that for 2 ≤ k < n every graph of order n and minimal degree at least n/k has circumference at least [n/(k - 1)]. Our aim here is to improve on this slightly, namely to show that the assertion holds without the integer sign, as conjectured by Katchalski. Although this seems to need a surprising amount of work, we feel it is worth it since the new result is best possible for all values of n and k (2 ≤ k < n) and implies a complete answer to the question above concerning the minimal circumference of a graph of order n and minimal degree d ≥ 2.
- Type
- Chapter
- Information
- A Tribute to Paul Erdos , pp. 97 - 104Publisher: Cambridge University PressPrint publication year: 1990
- 2
- Cited by