Super-pancyclic hypergraphs and bipartite graphs

Alexandr Kostochka, Ruth Luo, Dara Zirlin

Research output: Contribution to journalArticlepeer-review

Abstract

We find Dirac-type sufficient conditions for a hypergraph H with few edges to be hamiltonian. We also show that these conditions guarantee that H is super-pancyclic, i.e., for each A⊆V(H) with |A|≥3, H contains a Berge cycle with vertex set A. We mostly use the language of bipartite graphs, because every bipartite graph is the incidence graph of a multihypergraph. In particular, we extend some results of Jackson on the existence of long cycles in bipartite graphs where the vertices in one part have high minimum degree. Moreover, we prove a conjecture of Jackson from 1981 on long cycles in 2-connected bipartite graphs.

Original languageEnglish (US)
Pages (from-to)450-465
Number of pages16
JournalJournal of Combinatorial Theory. Series B
Volume145
DOIs
StatePublished - Nov 2020

Keywords

  • Berge cycles
  • Bipartite graphs
  • Extremal hypergraph theory

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Super-pancyclic hypergraphs and bipartite graphs'. Together they form a unique fingerprint.

Cite this