Previous |  Up |  Next


domination number; paired-domination number; tree
A set $S$ of vertices in a graph $G$ is called a paired-dominating set if it dominates $V$ and $\langle S\rangle $ contains at least one perfect matching. We characterize the set of vertices of a tree that are contained in all minimum paired-dominating sets of the tree.
[1] P. L. Hammer, P. Hansen and B. Simeone: Vertices belonging to all or to no maximum stable sets of a graph. SIAM J. Algebraic Discrete Math. 3 (1982), 511–522. DOI 10.1137/0603052 | MR 0679645
[2] C. M. Mynhardt: Vertices contained in every minimum dominating set of a tree. J. Graph Theory 31 (1999), 163–177. DOI 10.1002/(SICI)1097-0118(199907)31:3<163::AID-JGT2>3.0.CO;2-T | MR 1688945 | Zbl 0931.05063
[3] E. J. Cockayne, M. A. Henning and C. M. Mynhardt: Vertices contained in all or in no minimum total dominating set of a tree. Discrete Math. 260 (2003), 37–44. DOI 10.1016/S0012-365X(02)00447-8 | MR 1948372
[4] T. W. Haynes and P. J. Slater: Paired-domination in graphs. 32 (1998), Networks, 199–206. MR 1645415
[5] T. W. Haynes, M. A. Henning and P. J. Slater: Strong equality of domination parameters in trees. Discrete Math. 260 (2003), 77–87. DOI 10.1016/S0012-365X(02)00451-X | MR 1948376
[6] T. W. Haynes, S. T. Hedetniemi and P. J. Slater: Fundamentals of Domination in Graphs. Marcel Dekker, New York, 1998. MR 1605684
[7] Domination in Graphs: Advanced Topics. T. W. Haynes, S. T. Hedetniemi and P. J. Slater (eds.), Marcel Dekker, New York, 1998. MR 1605685 | Zbl 0883.00011
Partner of
EuDML logo