×

Forcing signed domination numbers in graphs. (English) Zbl 1164.05055

A function \(f:V(G)\to\{-1,1\}\) is called signed dominating function, if for each \(v\in V(G)\), \(\sum_{u\in N[v]}f(u)\geq1\). For a signed dominating function \(f\) of \(G\), the weight of \(f\) is \(w(f)=\sum_{v\in V}f(v)\). The signed dominating number \(\gamma_s(G)\) is the minimum weight of a signed dominating function on \(G\). A signed dominating function of weight \(\gamma_s(G)\) is called a \(\gamma_s(G)\)-function. A \(\gamma_s(G)\)-function \(f\) can also be represented by a set of ordered pairs \(S_f=\{(v,f(v)):v\in V\}\). A subset \(T\) of \(S_f\) is called a forcing subset of \(S_f\) if \(S_f\) is the unique extension of \(T\) to a \(\gamma_s(G)\)-function. The forcing signed domination number of \(S_f\), \(f(S_f,\gamma_s)\), is defined by \(f(S_f,\gamma_s)=\min\{| T| :T \text{ is a forcing subset of } S_f\}\) and the forcing signed domination number of \(G\), \(f(G,\gamma_s)\), is defined by \(f(G,\gamma_s)=\min\{f(S_f,\gamma_s):S_f\text{ is a }\gamma_s(G)\)-function

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: EuDML