×

A note on the lower bounds of signed domination number of a graph. (English) Zbl 0928.05052

Summary: Let \(G= (V,E)\) be a graph. For a function \(f: V\to\{-1, 1\}\), the weight of \(f\) is \(w(f)= \sum_{v\in V}f(v)\). For a vertex \(v\) in \(V\), we define \(f[v]=\sum_{u\in N[v]}f(u)\). A signed domination function of \(G\) is a function \(f: V\to\{-1,1\}\) such that \(f[v]\geq 1\) for all \(v\in V\). The signed domination number \(\gamma_{\text{s}}(G)\) of \(G\) is the minimum weight of a signed dominating function on \(G\). A signed dominating function of weight \(\gamma_{\text{s}}(G)\) we call a \(\gamma_{\text{s}}\)-function of \(G\). In this paper, we study the signed domination problem of general graphs, obtain some lower bounds of the signed domination number of a graph, show that these lower bounds are sharp, and extend a result in J. Dunbar, S. Hedetniemi, M. A. Hennig, and P. J. Slater [Signed domination in graphs. Graph theory, combinatorics, algorithms and applications, Vol. 1, 311-321 (1995; Zbl 0842.05051)].

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C35 Extremal problems in graph theory
05C22 Signed and weighted graphs

Citations:

Zbl 0842.05051
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Dunbar, J., Signed domination in graphs, (Graphy Theory, Combinatorics and Applications, vol. 1 (1995), Wiley: Wiley New York), 311-322 · Zbl 0842.05051
[2] Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), Macmillan: Macmillan London, and Elsevier, New York · Zbl 1134.05001
[3] Henning, M. A.; Slater, P. J., Inequality relating domination parameters in cubic graphs, Discrete Math., 158, 87-98 (1996) · Zbl 0858.05058
[4] Favaron, O., Signed domination in regular graphs, Discrete Math., 158, 287-293 (1995) · Zbl 0861.05033
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.