2018/12/02 by Austhof, Bethany, English, Sean
#05C07 #05C35 #05C65 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1812.00472
Given a graph G, we say a k-uniform hypergraph H on the same vertex set contains a Berge-G if there exists an injection ϕ:E(G)→ E(H) such that e⊆ϕ(e) for each edge e∈ E(G). A hypergraph H is Berge-G-saturated if H does not contain a Berge-G, but adding any edge to H creates a Berge-G. The saturation number for Berge-G, denoted satk(n,Berge-G) is the least number of edges in a k-uniform hypergraph that is Berge-G-saturated. We determine exactly the value of the saturation numbers for Berge stars. As a tool for our main result, we also prove the existence of nearly-regular k-uniform hypergraphs, or k-uniform hypergraphs in which every vertex has degree r or r-1 for some r∈ ℤ, and less than k vertices have degree r-1.