Signed domatic number of a graph (Q2565862)

Given a graph \(G=(V, E)\), the signed dominating function is a two-valued mapping \(f : V \rightarrow \{-1, 1\}\) such that, for each vertex \(v\in V\), \(\sum_{x\in N[v]} f(x) \geq 1\), where \(N[v]=N(v)\cup\{v\}\) is the closed neighborhood of \(v\). A signed dominating family on \(G\) is a set \(\{f_1, f_2, \ldots, f_d\}\) of signed dominating functions on \(G\) with the property that \(\sum_{i=1}^d f_i(x) \leq 1\) for each \(x\in V\). The maximum number of functions in a signed dominating family on \(G\), denoted by \(d_S(G)\), is the signed dominatic number of \(G\). The authors point out that \(d_S(G)\) is well defined and study its basic properties. Among others, they show that \(d_S(G)\) is an odd integer between \(1\) and the minimum degree of \(G\) plus one. They then determine \(d_S(G)\) in case \(G\) is a tree, a complete graph, a cycle, a fan, or a wheel, where a fan (wheel) is a graph obtained from a path (cycle) by adding a new vertex and edges joining it to all the vertices of the path (cycle).