| Tartalom: |
http://real.mtak.hu/39983/ |
| Archívum: |
MTA Könyvtár |
| Gyűjtemény: |
Status = Published
Type = Article
|
| Cím: |
The minimum number of vertices in uniform hypergraphs with given domination number
|
| Létrehozó: |
Bujtás, Csilla
Patkós, Balázs
Tuza, Zsolt
Vizer, Máté
|
| Kiadó: |
Elsevier
|
| Dátum: |
2017
|
| Téma: |
QA Mathematics / matematika
QA166-QA166.245 Graphs theory / gráfelmélet
|
| Tartalmi leírás: |
The textit(domination number) $gamma(cH)$ of a hypergraph $cH=(V(cH),E(cH))$ is the minimum size of a subset $Dsubset V(cH)$ of the vertices such that for every $vin V(cH)setminus D$ there exist a vertex $d in D$ and an edge $Hin E(cH)$ with $v,din 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(kgamma l)(2)$.
|
| Nyelv: |
magyar
|
| Típus: |
Article
PeerReviewed
info:eu-repo/semantics/article
|
| Formátum: |
text
|
| Azonosító: |
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
|
| Kapcsolat: |
https://doi.org/10.1016/j.disc.2016.07.007
10.1016/j.disc.2016.07.007
|
