A recurrence for bounds on dominating sets in \(k\)-majority tournaments
The electronic journal of combinatorics, Tome 18 (2011) no. 1
A $k$-majority tournament is realized by $2k-1$ linear orders on the set of vertices, where a vertex $u$ dominates $v$ if $u$ precedes $v$ in at least $k$ of the orders. Various properties of such tournaments have been studied, among them the problem of finding the size of a smallest dominating set. It is known that $2$-majority tournaments are dominated by $3$ vertices and that $k$-majority tournaments are dominated by $O(k \log k)$ vertices. However, precise values are not known even for $k=3$. We establish new upper bounds for the size of a smallest dominating set in $k$-majority tournaments that considerably improve upon previous bounds for small $k$. In particular our result shows that $3$-majority tournaments are dominated by at most $12$ vertices.
DOI :
10.37236/653
Classification :
05C20, 05C69, 91B14
Mots-clés : dominating set, majority tournament
Mots-clés : dominating set, majority tournament
@article{10_37236_653,
author = {Dror Fidler},
title = {A recurrence for bounds on dominating sets in \(k\)-majority tournaments},
journal = {The electronic journal of combinatorics},
year = {2011},
volume = {18},
number = {1},
doi = {10.37236/653},
zbl = {1234.05110},
url = {http://geodesic.mathdoc.fr/articles/10.37236/653/}
}
Dror Fidler. A recurrence for bounds on dominating sets in \(k\)-majority tournaments. The electronic journal of combinatorics, Tome 18 (2011) no. 1. doi: 10.37236/653
Cité par Sources :