×

Vertices contained in every minimum dominating set of a tree. (English) Zbl 0931.05063

Four special vertex subsets of a graph \(G\) are studied here: \({\mathcal A}(G)\) consists of all vertices which are contained in all minimum dominating sets, \({\mathcal N}(G)\) consists of all vertices which are not contained in any minimum dominating set, \({\mathcal A}_i(G)\) is the set of vertices contained in all minimum independent dominating sets, and \({\mathcal N}_i(G)\) contains the vertices which are not elements of any minimum independent dominating set. The relation \({\mathcal A}(G) \subseteq {\mathcal A}_i(G)\) does not necessarily hold, unless \(G\) contains a minimum dominating set which is also independent. Similarly for \({\mathcal N}(G)\) and \({\mathcal N}_i(G)\). These sets are characterized in this paper for trees by first examining paths, and then using a nicely developed tree pruning technique for rooted directed trees.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C05 Trees

Keywords:

dominating set; tree
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bollobás, J Graph Theory 3 pp 241– (1979)
[2] and A characterization of (?, i)-trees, submitted.
[3] Favaron, J Graph Theory 10 pp 429– (1986)
[4] Gunther, Congr Numer 101 pp 55– (1994)
[5] and Fundamentals of domination in graphs, Marcel Dekker, New York, 1998.
[6] Mitchell, Graph Theory and Comp pp 489– (1977)
[7] Siemes, Discrete Math 131 pp 279– (1994)
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.