Signed domination in graphs. (English) Zbl 0842.05051

Dunbar, Jean; Hedetniemi, Stephen; Henning, Michael A.; Slater, Peter J.

Alavi, Y. (ed.) et al., Graph theory, combinatorics, algorithms and applications. Vol. 1. Proceedings of the seventh quadrennial international conference on the theory and applications of graphs, Kalamazoo, MI, USA, June 1-5, 1992. New York, NY: Wiley. 311-321 (1995).

Summary: A two-valued function \(f\) defined on the vertices of a graph \(G= (V, E)\), \(f: V\to \{- 1, 1\}\), is a signed dominating function if the sum of its function values

•  Wolfram MathWorld

over any closed neighborhood is at least one. The weight of a signed dominating function is \(f(V)= \sum f(v)\), over all vertices \(v\in V\). The signed domination number

•  Wikipedia
•  Wolfram MathWorld

of a graph \(G\), denoted \(\gamma_s(G)\), equals the minimum weight of a signed dominating function of \(G\). In this paper we present properties of the signed domination number and establish upper and lower bounds for \(\gamma_s(G)\).
For the entire collection see [Zbl 0834.00037].

MSC:

05C35	Extremal problems in graph theory
05C05	Trees

Keywords:

tree; signed dominating function; weight; signed domination number