Hamiltonian chains in hypergraphs

Gyula Y. Katona, Henry Kierstead

Research output: Contribution to journalArticlepeer-review

126 Scopus citations

Abstract

A cyclic ordering of the vertices of a k-uniform hypergraph is called a hamiltonian chain if any k consecutive vertices in the ordering form an edge. For k = 2 this is the same as a hamiltonian cycle. We consider several natural questions about the new notion. The mam result is a Dirac-type theorem that provide a sufficient condition for finding hamiltonian chains in k-uniforrn hypergraphs with large (k - 1)-minimal degree. If it is more than (1 - 1/2k)n + 4 - k - 5/2k, than the hypergraph contains a hamiltonian chain.

Original languageEnglish (US)
Pages (from-to)205-212
Number of pages8
JournalJournal of Graph Theory
Volume30
Issue number3
DOIs
StatePublished - Mar 1999

Keywords

  • Dirac-type
  • Hamiltonian
  • Hypergraph

ASJC Scopus subject areas

  • Geometry and Topology

Fingerprint

Dive into the research topics of 'Hamiltonian chains in hypergraphs'. Together they form a unique fingerprint.

Cite this