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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
G. Chartrand and L. Lesniak, Graphs & Digraphs: Third Edition, Chapman & Hall, London, 1996.
M. Chellali and T.W. Haynes, “On paired and double domination in graphs,” Utilitas Math., vol. 67, pp. 161–171, 2005.
M. Chellali and T.W. Haynes, “Trees with unique minimum paired-dominating sets,” Ars Combin., vol. 73, pp. 3–12, 2004.
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., vol. 260, pp. 37–44, 2003.
O. Favaron and M.A. Henning, “Paired domination in claw-free cubic graphs,” Graphs and Combinatorics, vol. 20, pp. 447–456, 2004.
S. Fitzpatrick and B. Hartnell, “Paired-domination,” Discuss. Math.-Graph Theory, vol. 18, pp. 63–72, 1998.
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 Methods, vol. 3, no. 2, pp. 511–522, 1982.
T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998a.
T. W. Haynes, S.T. Hedetniemi, and P.J. Slater (eds.), Domination in Graphs: Advanced Topics, Marcel Dekker, New York, 1998b.
T.W. Haynes and P.J. Slater, “Paired-domination and the paired-domatic number,” Congr. Numer., vol. 109, pp. 65–72, 1995.
T.W. Haynes and P.J. Slater, “Paired-domination in graphs,” Networks, vol. 32, pp. 199–206, 1998.
C.M. Mynhardt, “Vertices contained in every minimum dominating set of a tree,” J. Graph Theory, vol. 31, no. 3, pp. 163–177, 1999.
K.E. Proffitt, T.W. Haynes, and P.J. Slater, “Paired-domination in grid graphs,” Congr. Numer., vol. 150, pp. 161–172, 2001.
H. Qiao, L. Kang, M. Cardei, and Ding-Zhu, “Paired-domination of trees,” J. Global Optimization, vol. 25, pp. 43–54, 2003.
E. Shan, L. Kang, and M.A. Henning, “A characterization of trees with equal total domination and paired-domination numbers,” Australasian J. Combinatorics, vol. 30, pp. 33–10, 2004.
Author information
Authors and Affiliations
Corresponding author
Additional information
Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal.
Rights and permissions
About this article
Cite this article
Henning, M.A., Plummer, M.D. Vertices Contained in all or in no Minimum Paired-Dominating Set of a Tree. J Comb Optim 10, 283–294 (2005). https://doi.org/10.1007/s10878-005-4107-3
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/s10878-005-4107-3