pith. sign in

arxiv: 1812.00472 · v1 · pith:UJZSEAJ7new · submitted 2018-12-02 · 🧮 math.CO

Nearly-Regular Hypergraphs and Saturation of Berge Stars

classification 🧮 math.CO
keywords berge-uniformhypergraphhypergraphssaturationbergedegreeedge
0
0 comments X
read the original abstract

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 $\phi:E(G)\to E(H)$ such that $e\subseteq\phi(e)$ for each edge $e\in 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 $\mathrm{sat}_k(n,\text{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\in \mathbb{Z}$, and less than $k$ vertices have degree $r-1$.

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.