آمار
| تعداد نشریات | 5 |
| تعداد شماره‌ها | 112 |
| تعداد مقالات | 1,271 |
| تعداد مشاهده مقاله | 1,238,778 |
| تعداد دریافت فایل اصل مقاله | 1,098,264 |
Directed domination in oriented hypergraphs | ||
| Communications in Combinatorics and Optimization | ||
| مقاله 9، دوره 4، شماره 2، اسفند 2019، صفحه 173-183 اصل مقاله (372.41 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2019.26466.1114 | ||
| نویسندگان | ||
| Yair Caro1؛ Adriana Hansberg* 2 | ||
| 1University of Haifa-Oranim | ||
| 276230 Queretaro, Mexico | ||
| چکیده | ||
| 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 - 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 $\overrightarrow{\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 \overrightarrow{\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$. | ||
| کلیدواژه‌ها | ||
| domination؛ directed domination؛ hypergraph | ||
| مراجع | ||
|
[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.
| ||
|
آمار تعداد مشاهده مقاله: 844 تعداد دریافت فایل اصل مقاله: 557 |
||