A note on saturation for Berge-G hypergraphs

DOI10.1007/S00373-019-02047-WMaRDI QIDQ2000585zbMATHOpenAlexFDO

Authors Christian Winter, Maria Axenovich

Publication date 28 June 2019

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.12734

zbMATH Keywords

saturationnon-uniformBerge-hypergraph

Mathematics Subject Classification ID

Hypergraphs (05C65)

Abstract: For a graph G, a hypergraph H is called Berge-G if there is a hypergraph H', isomorphic to H, containing all vertices of G, so that e is contained in f(e) for each edge e of G, where f is a bijection between E(G) and E(H'). The set of all Berge-G hypergraphs is denoted B(G). A hypergraph H is called Berge-G saturated if it does not contain any subhypergraph from B(G), but adding any new hyperedge of size at least 2 to H creates such a subhypergraph. Each Berge-G saturated hypergraph has at least |E(G)|-1 hyperedges. We show that for each graph G that is not a certain star and for any n at least |V(G)|, there is a Berge-G saturated hypergraph on n vertices and exactly |E(G)|-1 hyperedges. This solves a problem of finding a saturated hypergraph on n vertices with the smallest number of edges exactly.

Recommendations

• Saturation of Berge hypergraphs
• On saturation of Berge hypergraphs
• Linearity of saturation for Berge hypergraphs
• Nearly-regular hypergraphs and saturation of Berge stars
• Saturation number of Berge stars in random hypergraphs

Cites work

• scientific article; zbMATH DE number 2192110 (Why is no real title available?)
• A note on Ramsey numbers for Berge-\(G\) hypergraphs
• A survey of minimum saturated graphs
• Extremal results for Berge hypergraphs
• Linearity of saturation for Berge hypergraphs
• Monochromatic Hamiltonian Berge-cycles in colored complete uniform hypergraphs
• Saturated graphs with minimal number of edges
• Saturation of Berge hypergraphs
• The 3-colour Ramsey number of a 3-uniform Berge cycle
• The Minimum Size of Saturated Hypergraphs
• Triangle-Free Hypergraphs
• Turán numbers for Berge-hypergraphs and related extremal problems
• Uniformity thresholds for the asymptotic size of extremal Berge-\(F\)-free hypergraphs

Cited in

(9)

• On saturation of Berge hypergraphs
• Saturation numbers for Berge cliques
• Linear saturation numbers of Berge-\(C_3\) and Berge-\(C_4\)
• Nearly-regular hypergraphs and saturation of Berge stars
• Extremal results for Berge hypergraphs
• Linearity of saturation for Berge hypergraphs
• Saturation number of Berge stars in random hypergraphs
• Saturation for the 3-uniform loose 3-cycle
• Saturation of Berge hypergraphs

This page was built for publication: A note on saturation for Berge-\(G\) hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2000585)