Advertisement
Published in:
21-03-2019
On the k-domination number of digraphs
Published in: Journal of Combinatorial Optimization | Issue 3/2019
Log inActivate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
Let \(k\ge 1\) be an integer and let D be a digraph with vertex set V(D). A subset \(S\subseteq V(D)\) is called a k-dominating set if every vertex not in S has at least k predecessors in S. The k-domination number \(\gamma _{k}(D)\) of D is the minimum cardinality of a k-dominating set in D. We know that for any digraph D of order n, \(\gamma _{k}(D)\le n\). Obviously the upper bound n is sharp for a digraph with maximum in-degree at most \(k-1\). In this paper we present some lower and upper bounds on \(\gamma _{k}(D)\). Also, we characterize digraphs achieving these bounds. The special case \(k=1\) mostly leads to well known classical results.