Geodesic
The diameter of paired-domination vertex critical graphs
Czechoslovak Mathematical Journal, Tome 58 (2008) no. 4, pp. 887-897 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

In this paper we continue the study of paired-domination in graphs introduced by Haynes and Slater (Networks {\it 32} (1998), 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$. 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 _{{\rm pr}}(G - v) \gamma _{{\rm 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 _{{\rm pr}}(G) - 2)$. For $\gamma _{{\rm pr}}(G) \le 8$, we show that this lower bound is precisely the maximum diameter of a paired-domination vertex critical graph.
In this paper we continue the study of paired-domination in graphs introduced by Haynes and Slater (Networks {\it 32} (1998), 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$. 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 _{{\rm pr}}(G - v) \gamma _{{\rm 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 _{{\rm pr}}(G) - 2)$. For $\gamma _{{\rm pr}}(G) \le 8$, we show that this lower bound is precisely the maximum diameter of a paired-domination vertex critical graph.
Classification : 05C12, 05C35, 05C69
Keywords: paired-domination; vertex critical; bounds; diameter 
@article{CMJ_2008_58_4_a1,
     author = {Henning, Michael A. and Mynhardt, Christina M.},
     title = {The diameter of paired-domination vertex critical graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {887--897},
     year = {2008},
     volume = {58},
     number = {4},
     mrnumber = {2471154},
     zbl = {1174.05093},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_2008_58_4_a1/}
}
TY  - JOUR
AU  - Henning, Michael A.
AU  - Mynhardt, Christina M.
TI  - The diameter of paired-domination vertex critical graphs
JO  - Czechoslovak Mathematical Journal
PY  - 2008
SP  - 887
EP  - 897
VL  - 58
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/CMJ_2008_58_4_a1/
LA  - en
ID  - CMJ_2008_58_4_a1
ER  - 
%0 Journal Article
%A Henning, Michael A.
%A Mynhardt, Christina M.
%T The diameter of paired-domination vertex critical graphs
%J Czechoslovak Mathematical Journal
%D 2008
%P 887-897
%V 58
%N 4
%U http://geodesic.mathdoc.fr/item/CMJ_2008_58_4_a1/
%G en
%F CMJ_2008_58_4_a1
Henning, Michael A.; Mynhardt, Christina M. The diameter of paired-domination vertex critical graphs. Czechoslovak Mathematical Journal, Tome 58 (2008) no. 4, pp. 887-897. http://geodesic.mathdoc.fr/item/CMJ_2008_58_4_a1/

[1] Brigham, R. C., Chinn, P. Z., Dutton, R. D.: Vertex domination-critical graphs. Networks 18 (1988), 173-179. | DOI | MR | Zbl

[2] Chellali, M., Haynes, T. W.: Trees with unique minimum paired-dominating sets. Ars Combin. 73 (2004), 3-12. | MR | Zbl

[3] Chellali, M., Haynes, T. W.: Total and paired-domination numbers of a tree. AKCE Int. J. Graphs Comb. 1 (2004), 69-75. | MR | Zbl

[4] Chellali, M., Haynes, T. W.: On paired and double domination in graphs. Util. Math. 67 (2005), 161-171. | MR | Zbl

[5] Edwards, M.: Criticality concepts for paired domination in graphs. Master Thesis University of Victoria (2006).

[6] Favaron, O., Henning, M. A.: Paired domination in claw-free cubic graphs. Graphs Comb. 20 (2004), 447-456. | DOI | MR | Zbl

[7] Favaron, O., Sumner, D., Wojcicka, E.: The diameter of domination $k$-critical graphs. J. Graph Theory 18 (1994), 723-734. | DOI | MR | Zbl

[8] Fulman, J., Hanson, D., MacGillivray, G.: Vertex domination-critical graphs. Networks 25 (1995), 41-43. | DOI | MR | Zbl

[9] Fitzpatrick, S., Hartnell, B.: Paired-domination. Discuss. Math. Graph Theory 18 (1998), 63-72. | DOI | MR | Zbl

[10] Goddard, W., Haynes, T. W., Henning, M. A., Merwe, L. C. van der: The diameter of total domination vertex critical graphs. Discrete Math. 286 (2004), 255-261. | DOI | MR

[11] Haynes, T. W., Hedetniemi, S. T., Slater, P. J.: Fundamentals of Domination in Graphs. Marcel Dekker New York (1998). | MR | Zbl

[12] Haynes, T. W., Hedetniemi, S. T., Slater, P. J.: Domination in Graphs. Advanced Topics. Marcel Dekker New York (1998). | MR | Zbl

[13] Haynes, T. W., Henning, M. A.: Trees with large paired-domination number. Util. Math. 71 (2006), 3-12. | MR | Zbl

[14] Haynes, T. W., Slater, P. J.: Paired-domination in graphs. Networks 32 (1998), 199-206. | DOI | MR | Zbl

[15] Haynes, T. W., Slater, P. J.: Paired-domination and the paired-domatic number. Congr. Numerantium 109 (1995), 65-72. | MR | Zbl

[16] Henning, M. A.: Trees with equal total domination and paired-domination numbers. Util. Math. 69 (2006), 207-218. | MR | Zbl

[17] Henning, M. A.: Graphs with large paired-domination number. J. Comb. Optim. 13 (2007), 61-78. | DOI | MR | Zbl

[18] Henning, M. A., Plummer, M. D.: Vertices contained in all or in no minimum paired-dominating set of a tree. J. Comb. Optim. 10 (2005), 283-294. | DOI | MR | Zbl

[19] Proffitt, K. E., Haynes, T. W., Slater, P. J.: Paired-domination in grid graphs. Congr. Numerantium 150 (2001), 161-172. | MR | Zbl

[20] Qiao, H., Kang, L., Cardei, M., Du, Ding-Zhu: Paired-domination of trees. J. Glob. Optim. 25 (2003), 43-54. | DOI | MR | Zbl

[21] Sumner, D. P.: Critical concepts in domination. Discrete Math. 86 (1990), 33-46. | DOI | MR | Zbl

[22] Sumner, D. P., Blitch, P.: Domination critical graphs. J. Comb. Theory Ser. B 34 (1983), 65-76. | DOI | MR | Zbl

[23] Sumner, D. P., Wojcicka, E.: Graphs critical with respect to the domination number. Domination in Graphs: Advanced Topics (Chapter 16) T. W. Haynes, S. T. Hedetniemi, P. J. Slater Marcel Dekker New York (1998), 439-469. | MR | Zbl

[24] Wojcicka, E.: Hamiltonian properties of domination-critical graphs. J. Graph Theory 14 (1990), 205-215. | DOI | MR | Zbl