Maximum hypergraphs without regular subgraphs

Research output: Contribution to journalArticlepeer-review

Abstract

We show that an n-vertex hypergraph with no r-regular subgraphs has at most 2n-1+r-2edges. We conjecture that if n r, then every n-vertex hypergraph with no r-regular subgraphs having the maximum number of edges contains a full star, that is, 2n-1 distinct edges containing a given vertex. We prove this conjecture for n ≥ 425. The condition that n < r cannot be weakened.

Original languageEnglish (US)
Pages (from-to)151-166
Number of pages16
JournalDiscussiones Mathematicae - Graph Theory
Volume34
Issue number1
DOIs
StatePublished - 2014

Keywords

  • Hypergraphs
  • Regular graph
  • Set system
  • Subgraph

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Maximum hypergraphs without regular subgraphs'. Together they form a unique fingerprint.

Cite this