×

Domination and fractional domination in digraphs. (English) Zbl 1395.05069

Summary: In this paper, we investigate the relation between the (fractional) domination number of a digraph \(G\) and the independence number of its underlying graph, denoted by \(\alpha(G)\). More precisely, we prove that every digraph \(G\) on \(n\) vertices has fractional domination number at most \(2\alpha(G)\) and domination number at most \(2\alpha(G) \cdot \log{n}\). Both bounds are sharp.

MSC:

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

References:

[1] N. Alon, G. Brightwell, H.A. Kierstead, A.V. Kostochka and P. Winkler, Dominating sets in k-majority tournaments,Journal of Combinatorial Theory, Series B, 96, (2006), 374–387. · Zbl 1094.05040
[2] N. Bousquet, W. Lochet, and S. Thomass´e, A proof of the Erd˝os-Sands-SauerWoodrow conjecture, preprint.
[3] E. Chong and S. ˙Zak, An introduction to optimization. Fourth edition. John Wiley and Sons, 2013. · Zbl 1266.90001
[4] M. Chudnovsky, R. Kim, C.-H. Liu, P. Seymour, and S. Thomass´e, Domination in tournaments, Journal of Combinatorial Theory, Series B, 130, (2018), 98–113. · Zbl 1384.05090
[5] D. C. Fisher, Squaring a tournament: A proof of Dean’s conjecture, Journal of Graph Theory, 23(1), (1996), 43–48. · Zbl 0857.05042
[6] A. Gy´arf´as and D. P´alv¨olgyi, Domination in transitive colorings of tournaments, Journal of Combinatorial Theory, Series B, 107, (2014), 1–11.
[7] A. Gy´arf´as, G. Simonyi, and ´A. T´oth, Gallai colorings and domination in multipartite digraphs, Journal of Graph Theory, 71, (2012), 278–292. · Zbl 1305.05076
[8] A. Harutyunyan, T.-N. Le, A. Newman, and S. Thomass´e, Coloring dense digraphs, preprint. · Zbl 1379.05035
[9] A. Harutyunyan, T.-N. Le, S. Thomass´e, and H. Wu, Coloring tournaments: from local to global, preprint.
[10] T. W. Haynes, S. Hedetniemi, P. Slater, Fundamentals of domination in graphs. CRC Press, 1998. · Zbl 0890.05002
[11] A. Lagoutte, Quasi-P versus P, Master Thesis, ENS de Lyon, 2012.
[12] C. Lee, The domination number of a tournament, Korean Journal of Mathematics, 9(1), (2001), 21–28.
[13] N. Megiddo and U. Vishkin, On finding a minimum dominating set in a tournament, Theoretical Computer Science, 61, (1988), 307–316. · Zbl 0661.68064
[14] M. Molloy and B. Reed. Graph colouring and the probabilistic method. Springer, 2002. · Zbl 0987.05002
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.