×

Signed distance \(k\)-domatic numbers of graphs. (English) Zbl 1357.05118

Summary: Let \(k\) be a positive integer and let \(G\) be a simple graph with vertex set \(V(G)\). If \(u\) is a vertex of \(G\), then the open \(k\)-neighborhood of \(v\), denoted by \(N_{k,G}(v)\), is the set \(N_{k,G}(v) =\{u\mid u\neq v\) and \(d(u,v)\leq k\}\). \(N_{k,G}[v] = N_{k,G}(v)\cup\{v\}\) is the closed \(k\)-neighborhood of \(v\). A function \(f: V(G)\to\{-1,1\}\) is called a signed distance \(k\)-dominating function if \(\sum_{u\in N_{k,G[v]}} f(u)\geq 1\) for each vertex \(v\in V(G)\). A set \(\{f_1, f_2,\ldots, f_d\}\) of signed distance \(k\)-dominating functions on \(G\) with the property that \(\sum_{i =1}^d f_i(v)\leq 1\) for each \(v\in V(G)\), is called a signed distance \(k\)-dominating family (of functions) on \(G\). The maximum number of functions in a signed distance \(k\)-dominating family on \(G\) is the signed distance \(k\)-domatic number of \(G\), denoted by \(d_{k,s}(G)\). Note that \(d_{1,s}(D)\) is the classical signed domatic number \(d_s(D)\). In this paper we initiate the study of signed distance \(k\)-domatic numbers in graphs and we present some sharp upper bounds for \(d_{k,s}(G)\).

MSC:

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