Open AccessMaximum hypergraphs without regular subgraphs
Author(s) -
Jaehoon Kim,
Alexander V. Kostochka
Publication year - 2013
Publication title -
discussiones mathematicae graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.476
H-Index - 19
eISSN - 2083-5892
pISSN - 1234-3099
DOI - 10.7151/dmgt.1722
Subject(s) - hypergraph , combinatorics , mathematics , conjecture , vertex (graph theory) , discrete mathematics , graph
We show that an n-vertex hypergraph with no r-regular subgraphs has at most 2n−1+r−2 edges. 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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom