REAL

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

Bujtás, Csilla and Patkós, Balázs and Tuza, Zsolt and Vizer, Máté (2017) The minimum number of vertices in uniform hypergraphs with given domination number. Discrete Mathematics, 340 (11). pp. 2704-2713. ISSN 0012-365X

[img]
Preview
Text
main.pdf

Download (382kB) | Preview

Abstract

The \textit{domination number} $\gamma(\cH)$ of a hypergraph $\cH=(V(\cH),E(\cH))$ is the minimum size of a subset $D\subset V(\cH)$ of the vertices such that for every $v\in V(\cH)\setminus D$ there exist a vertex $d \in D$ and an edge $H\in E(\cH)$ with $v,d\in H$. We address the problem of finding the minimum number $n(k,\gamma)$ of vertices that a $k$-uniform hypergraph $\cH$ can have if $\gamma(\cH)\ge \gamma$ and $\cH$ 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}$.

Item Type: Article
Subjects: Q Science / természettudomány > QA Mathematics / matematika
Q Science / természettudomány > QA Mathematics / matematika > QA166-QA166.245 Graphs theory / gráfelmélet
Depositing User: Balázs Patkós
Date Deposited: 25 Sep 2016 17:12
Last Modified: 20 Sep 2017 08:32
URI: http://real.mtak.hu/id/eprint/39983

Actions (login required)

Edit Item Edit Item