×

Bounds on the weak domination number. (English) Zbl 0914.05041

A subset \(D\) of the vertex set \(V(G)\) of a graph \(G\) is called weak dominating in \(G\), if for each \(y\in V(G)- D\) there exists a vertex \(x\in D\) which is adjacent to \(y\) and whose degree is less than that of \(y\). The minimum number of vertices of a weak dominating set in \(G\) is the weak domination number \(\gamma_w(G)\) of \(G\). Various bounds for this number are found. This is seen from the titles of the sections: Sharp upper bounds on \(\gamma_w(G)\); Probabilistic upper bound on \(\gamma_w(G)\); Lower bound on \(\gamma_w(G)\).

MSC:

05C35 Extremal problems in graph theory
PDFBibTeX XMLCite