Name
Abstract | ||
|---|---|---|
The domination number
γ(H) of a hypergraph H=(V(H),E(H)) is the minimum size of a subset D⊂V(H) of the vertices such that for every v∈V(H)∖D there exist a vertex d∈D and an edge H∈E(H) with v,d∈H. We address the problem of finding the minimum number n(k,γ) of vertices that a k-uniform hypergraph H can have if γ(H)≥γ and H does not contain isolated vertices. We prove that n(k,γ)=k+Θ(k1−1∕γ)and also consider the s-wise dominating and the distance-l dominating version of the problem. In particular, we show that the minimum number ndc(k,γ,l) of vertices that a connected k-uniform hypergraph with distance-l domination number γ can have isroughly kγl2. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.disc.2016.07.007 | Discrete Mathematics |
Keywords | Field | DocType |
Hypergraph,Domination number,Distance domination,Multiple domination,Extremal problem | Discrete mathematics,Combinatorics,Vertex (geometry),Hypergraph,Constraint graph,Domination analysis,Mathematics | Journal |
Volume | Issue | ISSN |
340 | 11 | 0012-365X |
Citations | PageRank | References |
2 | 0.39 | 11 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Csilla Bujtás | 1 | 141 | 18.74 |
| Balázs Patkós | 2 | 85 | 21.60 |
| Zsolt Tuza | 3 | 1889 | 262.52 |
| Máté Vizer | 4 | 27 | 14.06 |