×

Domination number of certain infinite tournaments. (English) Zbl 1214.05042

Summary: We consider tournaments defined by several linear orderings of the vertex set according to some rule specifying the direction of each arc depending only on the order of the end vertices in each of the orderings. In the finite case, it was proved in N. Alon, G. Brightwell, H. Kierstead, A. Kostochka and P.Winkler, J. Comb. Theory, Ser. B 96, No. 3, 374–387, 736–738 (2006, Zbl 1094.05040) that the domination number of such tournaments is bounded in terms of the rule only. We show that for infinite tournaments, under some natural restrictions, the domination number is always finite, though in general cannot be bounded. We give some sufficient conditions under which there exists an upper bound in terms of the rule and/or the order types, and provide examples demonstrating that the bounds obtained are not very far from truth.

MSC:

05C20 Directed graphs (digraphs), tournaments
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Citations:

Zbl 1094.05040
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alon, N., Brightwell, G., Kierstead, H., Kostochka, A., Winkler, P.: Dominating sets in k-majority tournaments. J. Comb. Theory, Ser. B 96, 374–387 (2006) · Zbl 1088.05014 · doi:10.1016/j.jctb.2005.09.003
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.