×

Signed domination in graphs. (English) Zbl 0842.05051

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 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 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
PDFBibTeX XMLCite