Abstract
In this paper, we continue the study of paired-domination in graphs introduced by Haynes and Slater (1998) Networks 32: 199–206. A paired-dominating set of a graph G with no isolated vertex is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number of G, denoted by \(\gamma_{\rm pr}(G)\), is the minimum cardinality of a paired-dominating set of G. Let G be a connected graph of order n with minimum degree at least two. Haynes and Slater (1998) Networks 32: 199–206, showed that if n ≥ 6, then \(\gamma_{\rm pr}(G) \le 2n/3\). In this paper, we show that there are exactly ten graphs that achieve equality in this bound. For n ≥ 14, we show that \(\gamma_{\rm pr}(G) \le 2(n-1)/3\) and we characterize the (infinite family of) graphs that achieve equality in this bound.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Chellali M, Haynes TW (2004a) Trees with unique minimum paired-dominating sets. Ars Combin 73:3–12
Chellali M, Haynes TW (2004b) Total and paired-domination numbers of a tree. AKCE Int J Graphs Comb 1:69–75
Chellali M, Haynes TW (2005) On paired and double domination in graphs. Utilitas Math 67:161–171
Favaron O, Henning MA (2004) Paired domination in claw-free cubic graphs. Graphs Combin 20:447–456
Fitzpatrick S, Hartnell B (1998) Paired-domination. Discuss Math Graph Theory 18:63–72
Haynes TW, Hedetniemi ST, Slater PJ (1998a) Fundamentals of domination in graphs. Marcel Dekker, New York
Haynes TW, Hedetniemi ST, Slater PJ (eds) (1998b) Domination in graphs: advanced topics. Marcel Dekker, New York
Haynes TW, Slater PJ (1998) Paired-domination in graphs. Networks 32:199–206
Haynes TW, Slater PJ (1995) Paired-domination and the paired-domatic number. Congr Numer 109:65–72
Haynes TW, Henning MA (2006) Trees with large paired-domination number. Utilitas Math 71:3–12
Henning MA (2006) Trees with equal total domination and paired-domination numbers. Utilitas Math 69:207–218
Henning MA, Plummer MD (2005) Vertices contained in all or in no minimum paired-dominating set of a tree. J Comb. Optim. 10:283–294
Proffitt KE, Haynes TW, Slater PJ (2001) Paired-domination in grid graphs. Congr Numer 150:161–172
Qiao H, Kang L, Cardei M, Du D-Z (2003) Paired-domination of trees. J Global Optim 25:43–54
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. Graphs with large paired-domination number. J Comb Optim 13, 61–78 (2007). https://doi.org/10.1007/s10878-006-9014-8
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-006-9014-8