Directed domination in oriented hypergraphs

Document Type : Original paper

Authors

1 University of Haifa-Oranim

2 76230 Queretaro, Mexico

Abstract

ErdÖs [On Schutte problem, Math. Gaz. 47 (1963)] proved that every tournament on n vertices has a directed dominating set of at most log⁡(n+1) vertices, where log is the logarithm to base 2. He also showed that there is a tournament on n vertices with no directed domination set of cardinality less than log⁡n−2log⁡log⁡n+1. This notion of directed domination number has been generalized to arbitrary graphs by Caro and Henning in [Directed domination in oriented graphs, Discrete Appl. Math. (2012) 160:7--8.]. However, the generalization to directed r-uniform hypergraphs seems to be rare. Among several results, we prove the following upper and lower bounds on Γ→r−1(H(n,r)), the upper directed (r−1)-domination number of the complete r-uniform hypergraph on n vertices H(n,r), which is the main theorem of this paper:
c(ln⁡n)1r−1≤Γ→r−1(H(n,r))≤Cln⁡n,
where r is a positive integer and c=c(r)>0 and C=C(r)>0 are constants depending on r.

Keywords

Main Subjects

References

[1] B.D. Acharya, Domination in hypergraphs, AKCE Int. J. Graphs Comb. 4 (2007), no. 2, 117–126.
[2] , Domination in hypergraphs ii. new directions, Proc. Int. Conf.–ICDM, 2008, pp. 1–16.
[3] Y. Caro and M.A. Henning, A greedy partition lemma for directed domination, Discrete Optim. 8 (2011), no. 3, 452–458.
[4] Y. Caro and M.A. Henning, Directed domination in oriented graphs, Discrete Appl. Math. 160 (2012), no. 7-8, 1053–1063.
[5] P. Erdős, On schütte problem, Math. Gaz. 47 (1963), 220–222.
[6] A. Harutyunyan, T.-N. Le, A. Newman, and S. Thomass´e, Domination and fractional domination in digraphs, Electr. J. Combin. 25 (2018), no. 3, #P3.32, pp. 9.
[7] B.K. Jose and Z. Tuza, Hypergraph domination and strong independence, Appl. Anal. Discrete Math. 3 (2009), no. 2, 347–358.
[8] D. Korándi and B. Sudakov, Domination in 3-tournaments, J. Combin. Theory Ser. A 146 (2017), 165–168.
 
Communications in Combinatorics and Optimization
Volume 4, Issue 2
Special issue in honour of Prof. Lutz Volkmann
December 2019
Pages 173-183

Files

Share

How to cite

Statistics