pith. machine review for the scientific record. sign in

arxiv: 1810.12734 · v1 · pith:M772AWIDnew · submitted 2018-10-30 · 🧮 math.CO

A note on saturation for Berge-G hypergraphs

classification 🧮 math.CO
keywords berge-ghypergraphsaturatedleastverticescalledexactlygraph
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.