Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420683 | Discrete Applied Mathematics | 2009 | 6 Pages |
Let G=(V,E)G=(V,E) be a graph. A function f:V→{−1,+1}f:V→{−1,+1} defined on the vertices of GG is a signed total dominating function if the sum of its function values over any open neighborhood is at least one. A signed total dominating function ff is minimal if there does not exist a signed total dominating function gg, f≠gf≠g, for which g(v)≤f(v)g(v)≤f(v) for every v∈Vv∈V. The weight of a signed total dominating function is the sum of its function values over all vertices of GG. The upper signed total domination number of GG is the maximum weight of a minimal signed total dominating function on GG. In this paper we present a sharp upper bound on the upper signed total domination number of an arbitrary graph. This result generalizes previous results for regular graphs and nearly regular graphs.