Signed \(k\)-domatic numbers of digraphs (Q1940993): Difference between revisions

In this article, two parameters of a directed graph \(D\) are introduced. Given a vertex \(v\) in \(D\), denote by \(N^-[v]\) the set of vertices with an arc towards \(v\) plus \(v\) itself. Given an integer \(k\geq 1\), a function \(f\) from the vertex set \(V\) to \(\{+1,-1\}\) is called \textit{signed \(k\)-dominating} if \(\sum_{u\in N^-[v]}f(u)\geq k\) for every \(k\). The first introduced parameter is the \textit{signed \(k\)-domination number} of \(D\) defined as \[ \min=\{\sum_{v\in V}f(v)\mid f \text{ signed \(k\)-dominating}\}. \] The second parameter is the maximum size of a set \(F\) of signed \(k\)-dominating functions such that \(\sum_{f\in F}f(v)\leq 1\) for all \(v\in V\). It is called the \textit{signed \(k\)-domatic number} of \(D\). The authors obtain several bounds mainly for the signed \(k\)-domatic number, mostly in terms of minimum and maximum (in) degree of \(D\).