Some remarks on the signed domatic number of graphs with small minimum degree

Let G be a finite and simple graph with the vertex set V(G), and let f : V(G) -> {- 1, 1} be a two-valued function. If Sigma(x is an element of N[nu])f(x) >= 1 for each nu is an element of V(G), where N[nu] is the closed neighborhood of nu, then f is a signed dominating function on G. A set {f(1), f(2), ... ,f(d)} of signed dominating functions on G with the property that Sigma(d)(i=1)fi(x) <= 1 for each x is an element of V(G) is called a signed dominating family (of functions) on G. The maximum number of functions in a signed dominating family on G is the signed domatic number of G, denoted by d(S)(G). If nu is a vertex of a graph G, then d(G)(nu) is the degree of the vertex nu. In this note we show that d(S)(G) = 1 if either G contains a vertex of degree 3 or G contains a cycle C(p) = u(1)u(2) ... u(p)u(1) of length p >= 4 such that p not equivalent to 0 (mod 3) and d(G)(u(i)) <= 3 for 1 <= i <= p - 1. In particular, d(S)(G) = 1 for each grid and each cylinder different from the cycle C(p) with the property that p equivalent to 0 (mod 3). (C) 2009 Elsevier Ltd. All rights reserved.