The longest cycle of a graph with a large minimal degree

Research output: Contribution to journalArticle

10 Scopus citations

Abstract

We show that every graph G on n vertices with minimal degree at least n/k contains a cycle of length at least [n/(k − 1)]. This verifies a conjecture of Katchalski. When k = 2 our result reduces to the classical theorem of Dirac that asserts that if all degrees are at least 1/2n then G is Hamiltonian.

Original languageEnglish (US)
Pages (from-to)123-127
Number of pages5
JournalJournal of Graph Theory
Volume10
Issue number1
DOIs
StatePublished - Jan 1 1986
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Fingerprint Dive into the research topics of 'The longest cycle of a graph with a large minimal degree'. Together they form a unique fingerprint.

Cite this