Graphs with large paired-domination number. (English) Zbl 1108.05069

Summary: In this paper, we continue the study of paired-domination in graphs introduced by T. W. Haynes and P. J. Slater [Networks 32, 199–206 (1998; Zbl 0997.05074)]. 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_{\text{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 [loc. cit.] showed that if \(n \geq 6\), then \(\gamma_{\text{pr}}(G) \leq 2n/3\). In this paper, we show that there are exactly ten graphs that achieve equality in this bound. For \(n \geq 14\), we show that \(\gamma_{\text{pr}}(G) \leq 2(n-1)/3\) and we characterize the (infinite family of) graphs that achieve equality in this bound.


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


Zbl 0997.05074
Full Text: DOI


[1] Chellali M, Haynes TW (2004a) Trees with unique minimum paired-dominating sets. Ars Combin 73:3–12 · Zbl 1082.05023
[2] Chellali M, Haynes TW (2004b) Total and paired-domination numbers of a tree. AKCE Int J Graphs Comb 1:69–75 · Zbl 1066.05101
[3] Chellali M, Haynes TW (2005) On paired and double domination in graphs. Utilitas Math 67:161–171 · Zbl 1069.05058
[4] Favaron O, Henning MA (2004) Paired domination in claw-free cubic graphs. Graphs Combin 20:447–456 · Zbl 1054.05074
[5] Fitzpatrick S, Hartnell B (1998) Paired-domination. Discuss Math Graph Theory 18:63–72 · Zbl 0916.05061
[6] Haynes TW, Hedetniemi ST, Slater PJ (1998a) Fundamentals of domination in graphs. Marcel Dekker, New York
[7] Haynes TW, Hedetniemi ST, Slater PJ (eds) (1998b) Domination in graphs: advanced topics. Marcel Dekker, New York
[8] Haynes TW, Slater PJ (1998) Paired-domination in graphs. Networks 32:199–206 · Zbl 0997.05074
[9] Haynes TW, Slater PJ (1995) Paired-domination and the paired-domatic number. Congr Numer 109:65–72 · Zbl 0904.05052
[10] Haynes TW, Henning MA (2006) Trees with large paired-domination number. Utilitas Math 71:3–12 · Zbl 1112.05078
[11] Henning MA (2006) Trees with equal total domination and paired-domination numbers. Utilitas Math 69:207–218 · Zbl 1100.05070
[12] 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 · Zbl 1122.05071
[13] Proffitt KE, Haynes TW, Slater PJ (2001) Paired-domination in grid graphs. Congr Numer 150:161–172 · Zbl 0988.05067
[14] Qiao H, Kang L, Cardei M, Du D-Z (2003) Paired-domination of trees. J Global Optim 25:43–54 · Zbl 1013.05055
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.