TY - JOUR
ID - 13862
TI - Directed domination in oriented hypergraphs
JO - Communications in Combinatorics and Optimization
JA - CCO
LA - en
SN - 2538-2128
AU - Caro, Yair
AU - Hansberg, Adriana
AD - University of Haifa-Oranim
AD - 76230 Queretaro, Mexico
Y1 - 2019
PY - 2019
VL - 4
IS - 2
SP - 173
EP - 183
KW - domination
KW - directed domination
KW - hypergraph
DO - 10.22049/cco.2019.26466.1114
N2 - ErdH{o}s [On Sch"utte 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 - 2 log 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 $ora{Gamma}_{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)^{frac{1}{r-1}} le ora{Gamma}_{r-1}(H(n,r)) le C ln n,]where $r$ is a positive integer and $c= c(r) > 0$ and $C = C(r) > 0$ are constants depending on $r$.
UR - http://comb-opt.azaruniv.ac.ir/article_13862.html
L1 - http://comb-opt.azaruniv.ac.ir/article_13862_c7627d5b92f3a70d4057950f050d2d68.pdf
ER -