Upper bounds on the signed total domatic number of graphs
Let G G be a graph with the vertex set V(G) V ( G ) , and let f:V(G)?{?1,1} f : V ( G ) ? { ? 1 , 1 } be a two-valued function. If G G has no isolated vertices and ?x?N(v)f(x)?1 ? x ? N ( v ) f ( x ) ? 1 for each v?V(G) v ? V ( G ) , where N(v) N ( v ) is the neighborhood of v v , then f f is a signed total dominating function on G G . A set {f1,f2,,fd} { f 1 , f 2 ,  , f d } of signed total dominating functions on G G with the property that ? i = 1 d f i ( x ) ? 1 for each x?V(G) x ? V ( G ) is called a signed total dominating family (of functions) on G G . The maximum number of functions in a signed total dominating family on G G is the signed total domatic number of G G , denoted by d t S ( G ) . In this article we mainly present upper bounds on d t S ( G ) , in particular for regular graphs. As an application of these bounds, we show that d t S ( G ) ? n ? 3 for any graph G G of order n?4 n ? 4 without isolated vertices. Furthermore, we prove the NordhausGaddum inequality d t S ( G ) + d t S ( G  ) ? n ? 3 for graphs G G and G  of order n?7 n ? 7 without isolated vertices, where G  is the complement of G G .
signed total domatic number signed total dominating function signed total dominating family nordhausgaddum inequality