×

On the domination number of digraphs. (English) Zbl 1463.05401

Summary: A vertex subset \(S\) of a digraph \(D\) is called a dominating set of \(D\) if every vertex not in \(S\) is adjacent from at least one vertex in \(S\). The domination number of \(D\), denoted by \(\gamma(D)\), is the minimum cardinality of a dominating set of \(D\). We characterize the rooted trees and connected contrafunctional digraphs \(D\) of order \(n\) satisfying \(\gamma(D)=\lceil n/2\rceil\). Moreover, we show that for every digraph \(D\) of order \(n\) with minimum in-degree at least one, \(\gamma(D)\leq (k+1)n/(2k+1)\), where \(2k+1\) is the length of a shortest odd directed cycle in \(D\), and we characterize the corresponding digraphs achieving this upper bound. In particular, if \(D\) contains no odd directed cycles, then \(\gamma(D)\leq n/2\).

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C20 Directed graphs (digraphs), tournaments
PDFBibTeX XMLCite