Dominating sets in \(k\)-majority tournaments. (Q2490838): Difference between revisions

The \(k\)-majority tournament determined by \(2k-l\) linear orderings of a finite vertex set \(V\) is the directed graph \(T\) on \(V\) in which \(uv\) is an arc if and only if \(u\) precedes \(v\) in at least \(k\) of the orderings. Let \(F(k)\) denote the maximum of the size of a minimum dominating set of \(T\) over all \(k\)-majority tournaments \(T\) (with no restriction on the size of \(V)\). The authors' main results are that \(F(2)=3\), \(F(3)\geq 4\), and that \(F(k)=\Omega(k/\log k)\) for \(k\geq 3\).