×

Dominating sets in \(k\)-majority tournaments. (English) Zbl 1094.05040

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\).

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C20 Directed graphs (digraphs), tournaments
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] G. Andrews, The theory of partitions, Encyclopedia of Mathematics and its Applications, vol. 2, Cambridge University Press, Cambridge, 1984.; G. Andrews, The theory of partitions, Encyclopedia of Mathematics and its Applications, vol. 2, Cambridge University Press, Cambridge, 1984.
[2] H. Harborth, Integral distances in point sets, in: P.L. Butzer, et al. (Eds.), Karl der Grosse und sein Nachwirken, 1200 Jahre Kultur und Wissenschaft in Europa. Band 2: Mathematisches Wissen, Turnhout: Brepols, 1998, pp. 213-224.; H. Harborth, Integral distances in point sets, in: P.L. Butzer, et al. (Eds.), Karl der Grosse und sein Nachwirken, 1200 Jahre Kultur und Wissenschaft in Europa. Band 2: Mathematisches Wissen, Turnhout: Brepols, 1998, pp. 213-224. · Zbl 0956.52021
[3] H. Harborth, L. Piepmeyer, Points sets with small integral distances, in: Applied Geometry and Discrete Mathematics, Festschr, 65th Birthday Victor Klee, DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 4 (1991) 319-324.; H. Harborth, L. Piepmeyer, Points sets with small integral distances, in: Applied Geometry and Discrete Mathematics, Festschr, 65th Birthday Victor Klee, DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 4 (1991) 319-324. · Zbl 0739.52014
[4] H. Harborth, L. Piepmeyer, Two-distance sets and the golden ratio, in: G.E. Bergum, et al. (Eds.), Applications of Fibonacci numbers, Proceedings of the Fifth International Conference on Fibonacci numbers and their Applications, vol. 5, University of St. Andrews, Scotland, July 20-24, 1992. Kluwer Academic Publishers, Dordrecht, 1993, pp. 279-288.; H. Harborth, L. Piepmeyer, Two-distance sets and the golden ratio, in: G.E. Bergum, et al. (Eds.), Applications of Fibonacci numbers, Proceedings of the Fifth International Conference on Fibonacci numbers and their Applications, vol. 5, University of St. Andrews, Scotland, July 20-24, 1992. Kluwer Academic Publishers, Dordrecht, 1993, pp. 279-288. · Zbl 0789.05035
[5] Menger, K., Untersuchungen über allgemeine Metrik, Math. Ann., 100, 75-163 (1928) · JFM 54.0622.02
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.