The global point-set domination number of a graph. (English) Zbl 0871.05036

The point-set domination number of a graph is a variant of the domination number. A subset \(D\) of the vertex set \(V(G)\) of a graph \(G\) is called point-set dominating (psd-set), if for every set \(S\subset V(G)-D\) there exists a vertex \(v\in D\) such that \(S\cup\{v\}\) induces a connected subgraph of \(G\). If \(D\) is a psd-set simultaneously of \(G\) and of its complement \(\overline{G}\), then \(D\) is called global point-set dominating. The minimum number of vertices of a psd-set (or of a global psd-set) in \(G\) is the point-set domination number (or global point-set domination number, respectively) of \(G\). Some inequalities for these numbers are found.


05C35 Extremal problems in graph theory