(1) School of Mathematical Sciences, University of KwaZulu-Natal, Pietermaritzburg, 3209, South Africa;(2) Department of Mathematics, Vanderbilt University, Nashville, TN 37240, USA
Abstract:
A set S of vertices in a graph G is a paired-dominating set of G if every vertex of G is adjacent to some vertex in S and if the subgraph induced by S contains a perfect matching. We characterize the set of vertices of a tree that are contained in all, or in no, minimum paired-dominating sets of the tree. Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal.
