The diameter of paired-domination vertex critical graphs. (English) Zbl 1174.05093

Summary: In this paper we continue the study of paired-domination in graphs introduced by Teresa W. Haynes and Peter 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\). The graph  \(G\) is paired-domination vertex critical if for every vertex  \(v\) of  \(G\) that is not adjacent to a vertex of degree one, \(\gamma _{\text{pr}}(G - v) < \gamma _{\text{pr}}(G)\). We characterize the connected graphs with minimum degree one that are paired-domination vertex critical and we obtain sharp bounds on their maximum diameter. We provide an example which shows that the maximum diameter of a paired-domination vertex critical graph is at least \(\frac 32(\gamma _{\text{pr}}(G) - 2)\). For \(\gamma _{\text{pr}}(G) \leq 8\), we show that this lower bound is precisely the maximum diameter of a paired-domination vertex critical graph.


05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C35 Extremal problems in graph theory


Zbl 0997.05074
Full Text: DOI EuDML Link


[1] R. C. Brigham, P. Z. Chinn, R. D. Dutton: Vertex domination-critical graphs. Networks 18 (1988), 173–179. · Zbl 0658.05042
[2] M. Chellali, T. W. Haynes: Trees with unique minimum paired-dominating sets. Ars Combin. 73 (2004), 3–12. · Zbl 1082.05023
[3] M. Chellali, T. W. Haynes: Total and paired-domination numbers of a tree. AKCE Int. J. Graphs Comb. 1 (2004), 69–75. · Zbl 1066.05101
[4] M. Chellali, T. W. Haynes: On paired and double domination in graphs. Util. Math. 67 (2005), 161–171. · Zbl 1069.05058
[5] M. Edwards: Criticality concepts for paired domination in graphs. Master Thesis. University of Victoria, 2006.
[6] O. Favaron, M. A. Henning: Paired domination in claw-free cubic graphs. Graphs Comb. 20 (2004), 447–456. · Zbl 1054.05074
[7] O. Favaron, D. Sumner, E. Wojcicka: The diameter of domination k-critical graphs. J. Graph Theory 18 (1994), 723–734. · Zbl 0807.05042
[8] J. Fulman, D. Hanson, G. MacGillivray: Vertex domination-critical graphs. Networks 25 (1995), 41–43. · Zbl 0820.05038
[9] S. Fitzpatrick, B. Hartnell: Paired-domination. Discuss. Math. Graph Theory 18 (1998), 63–72. · Zbl 0916.05061
[10] W. Goddard, T. W. Haynes, M. A. Henning, L. C. van der Merwe: The diameter of total domination vertex critical graphs. Discrete Math. 286 (2004), 255–261. · Zbl 1055.05113
[11] T. W. Haynes, S. T. Hedetniemi, P. J. Slater: Fundamentals of Domination in Graphs. Marcel Dekker, New York, 1998. · Zbl 0890.05002
[12] Domination in Graphs. Advanced Topics (T. W. Haynes, S. T. Hedetniemi, P. J. Slater, eds.). Marcel Dekker, New York, 1998.
[13] T. W. Haynes, M. A. Henning: Trees with large paired-domination number. Util. Math. 71 (2006), 3–12. · Zbl 1112.05078
[14] T. W. Haynes, P. J. Slater: Paired-domination in graphs. Networks 32 (1998), 199–206. · Zbl 0997.05074
[15] T. W. Haynes, P. J. Slater: Paired-domination and the paired-domatic number. Congr. Numerantium 109 (1995), 65–72. · Zbl 0904.05052
[16] M. A. Henning: Trees with equal total domination and paired-domination numbers. Util. Math. 69 (2006), 207–218. · Zbl 1100.05070
[17] M. A. Henning: Graphs with large paired-domination number. J. Comb. Optim. 13 (2007), 61–78. · Zbl 1108.05069
[18] M. A. Henning, M. D. Plummer: Vertices contained in all or in no minimum paired-dominating set of a tree. J. Comb. Optim. 10 (2005), 283–294. · Zbl 1122.05071
[19] K. E. Proffitt, T. W. Haynes, P. J. Slater: Paired-domination in grid graphs. Congr. Numerantium 150 (2001), 161–172. · Zbl 0988.05067
[20] H. Qiao, L. Kang, M. Cardei, Ding-Zhu Du: Paired-domination of trees. J. Glob. Optim. 25 (2003), 43–54. · Zbl 1013.05055
[21] D. P. Sumner: Critical concepts in domination. Discrete Math. 86 (1990), 33–46. · Zbl 0725.05049
[22] D. P. Sumner, P. Blitch: Domination critical graphs. J. Comb. Theory Ser. B 34 (1983), 65–76. · Zbl 0512.05055
[23] D. P. Sumner, E. Wojcicka: Graphs critical with respect to the domination number. Domination in Graphs: Advanced Topics (Chapter 16) (T. W. Haynes, S. T. Hedetniemi, P. J. Slater, eds.). Marcel Dekker, New York, 1998, pp. 439–469. · Zbl 0891.05043
[24] E. Wojcicka: Hamiltonian properties of domination-critical graphs. J. Graph Theory 14 (1990), 205–215. · Zbl 0702.05058
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.