The minimum number of vertices in uniform hypergraphs with given domination number

Abstract

The \textit{domination number} $\gamma (\mathcal{H})$ of a hypergraph $\mathcal{H}=(V(\mathcal{H}),E(\mathcal{H})$ is the minimum size of a subset $D\subset V(\mathcal{H}$ of the vertices such that for every $v\in V(\mathcal{H})\setminus D$ there exist a vertex $d\in D$ and an edge $H\in E(\mathcal{H})$ with $v,d\in H$. We address the problem of finding the minimum number $n(k,\gamma )$ of vertices that a $k$-uniform hypergraph $\mathcal{H}$ can have if $\gamma (\mathcal{H})\ge \gamma$ and $\mathcal{H}$ does not contain isolated vertices. We prove that $$n(k,\gamma )=k+\Theta (k^{1-1/\gamma })$$ and also consider the $s$-wise dominating and the distance-$l$ dominating version of the problem. In particular, we show that the minimum number $n_{dc}(k,\gamma ,l)$ of vertices that a connected $k$-uniform hypergraph with distance-$l$ domination number $\gamma$ can have is roughly $\frac{k\gamma l}{2}$

accepted to Discrete Mathematics