Directed domination in oriented hypergraphs

DOI10.22049/CCO.2019.26466.1114MaRDI QIDQ5242948zbMATH OpenOpenAlexFDO

Authors Yair Caro, Adriana Hansberg

Publication date 8 November 2019

Full work available at URL https://arxiv.org/abs/1904.02351

zbMATH Keywords

dominationhypergraphdirected domination

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Hypergraphs (05C65)

Abstract: 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 $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 $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$.

Recommendations

• scientific article; zbMATH DE number 1161338
• Domination number of certain infinite tournaments
• Directed domination in oriented graphs
• Matching and domination numbers in \(r\)-uniform hypergraphs
• A greedy partition lemma for directed domination

Cites work

• A greedy partition lemma for directed domination
• Directed domination in oriented graphs
• Domination and fractional domination in digraphs
• Domination in 3-tournaments
• Domination in hypergraphs
• Hypergraph domination and strong independence
• On a Problem in Graph Theory

Cited in

(3)

• A greedy partition lemma for directed domination
• Directed Moore hypergraphs
• Directed domination in oriented graphs

This page was built for publication: Directed domination in oriented hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5242948)