Covering 3-uniform hypergraphs by vertex-disjoint tight paths

Jie Han*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

For α > 0 and large integer n, let H be an n-vertex 3-uniform hypergraph such that every pair of vertices is in at least (Formula presented.) edges. We show that (Formula presented.) contains two vertex-disjoint tight paths whose union covers the vertex set of (Formula presented.). The quantity two here is best possible and the degree condition is asymptotically best possible. This result also has an interpretation as the deficiency problems, recently introduced by Nenadov, Sudakov, and Wagner: every such (Formula presented.) can be made Hamiltonian by adding at most two vertices and all triples intersecting them.

Original languageEnglish
Pages (from-to)782-802
Number of pages21
JournalJournal of Graph Theory
Volume101
Issue number4
DOIs
Publication statusPublished - Dec 2022

Keywords

  • Hamilton cycle
  • tight path

Fingerprint

Dive into the research topics of 'Covering 3-uniform hypergraphs by vertex-disjoint tight paths'. Together they form a unique fingerprint.

Cite this