|
|
|
|
directed domination in oriented hypergraphs
|
|
|
|
|
|
|
|
نویسنده
|
caro yair ,hansberg adriana
|
|
منبع
|
communications in combinatorics and optimization - 2019 - دوره : 4 - شماره : 2 - صفحه:173 -183
|
|
چکیده
|
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 logn−2loglogn+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(lnn)1r−1≤γ→r−1(h(n,r))≤clnn, where r is a positive integer and c=c(r)>0 and c=c(r)>0 are constants depending on r.
|
|
کلیدواژه
|
domination ,directed domination ,hypergraph
|
|
آدرس
|
university of haifa-oranim, dep. of mathematics, uniusa, unam juriquilla, instituto de matematicas, mexico
|
|
پست الکترونیکی
|
ahansberg@im.unam.mx
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Authors
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|