Point-set domination number of a graph. (English) Zbl 0772.05055

Sampathkumar, E.; Pushpa Latha, L.

Indian J. Pure Appl. Math. 24, No. 4, 225-229 (1993).

Summary: A set \(D\) of vertices in a connected graph \(G\) is a psd-set if for every set \(S\subseteq V-D\) there exists a vertex \(\nu\in D\) such that the subgraph \(\langle S\cup\{\nu\}\rangle\) induced by \(S\cup\{\nu\}\) is connected. The point-set domination number \(\gamma_ p(G)\) of \(G\) is the minimum cardinality of a psd-set. Besides some bounds, exact values of \(\gamma_ p(G)\) are determined when \(G\) is a tree, block graph and cactus. A generalization of \(\gamma_ p(G)\) is also considered.

MSC:

05C35	Extremal problems in graph theory
05C99	Graph theory

Keywords:

connected graph; point-set domination number; tree; block graph; cactus