The diameter of paired-domination vertex critical graphs

Michael A. Henning; Christina M. Mynhardt

Czechoslovak Mathematical Journal (2008)

  • Volume: 58, Issue: 4, page 887-897
  • ISSN: 0011-4642

Abstract

top
In this paper we continue the study of paired-domination in graphs introduced by Haynes and Slater (Networks 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 γ 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, γ pr ( G - v ) < γ 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 3 2 ( γ pr ( G ) - 2 ) . For γ pr ( G ) ≤ 8 , we show that this lower bound is precisely the maximum diameter of a paired-domination vertex critical graph.

How to cite

top

Henning, Michael A., and Mynhardt, Christina M.. "The diameter of paired-domination vertex critical graphs." Czechoslovak Mathematical Journal 58.4 (2008): 887-897. <http://eudml.org/doc/37874>.

@article{Henning2008,
abstract = {In this paper we continue the study of paired-domination in graphs introduced by Haynes and Slater (Networks 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\{3\}\{2\}(\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.},
author = {Henning, Michael A., Mynhardt, Christina M.},
journal = {Czechoslovak Mathematical Journal},
keywords = {paired-domination; vertex critical; bounds; diameter; paired-domination number; paired-dominating set; vertex critical; bounds; diameter},
language = {eng},
number = {4},
pages = {887-897},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {The diameter of paired-domination vertex critical graphs},
url = {http://eudml.org/doc/37874},
volume = {58},
year = {2008},
}

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
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 58
IS - 4
SP - 887
EP - 897
AB - In this paper we continue the study of paired-domination in graphs introduced by Haynes and Slater (Networks 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{3}{2}(\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.
LA - eng
KW - paired-domination; vertex critical; bounds; diameter; paired-domination number; paired-dominating set; vertex critical; bounds; diameter
UR - http://eudml.org/doc/37874
ER -

References

top
  1. Brigham, R. C., Chinn, P. Z., Dutton, R. D., 10.1002/net.3230180304, Networks 18 (1988), 173-179. (1988) Zbl0658.05042MR0953920DOI10.1002/net.3230180304
  2. Chellali, M., Haynes, T. W., Trees with unique minimum paired-dominating sets, Ars Combin. 73 (2004), 3-12. (2004) Zbl1082.05023MR2098744
  3. Chellali, M., Haynes, T. W., Total and paired-domination numbers of a tree, AKCE Int. J. Graphs Comb. 1 (2004), 69-75. (2004) Zbl1066.05101MR2120712
  4. Chellali, M., Haynes, T. W., On paired and double domination in graphs, Util. Math. 67 (2005), 161-171. (2005) Zbl1069.05058MR2137931
  5. Edwards, M., Criticality concepts for paired domination in graphs, Master Thesis University of Victoria (2006). (2006) 
  6. Favaron, O., Henning, M. A., 10.1007/s00373-004-0577-9, Graphs Comb. 20 (2004), 447-456. (2004) Zbl1054.05074MR2108391DOI10.1007/s00373-004-0577-9
  7. Favaron, O., Sumner, D., Wojcicka, E., 10.1002/jgt.3190180708, J. Graph Theory 18 (1994), 723-734. (1994) Zbl0807.05042MR1297193DOI10.1002/jgt.3190180708
  8. Fulman, J., Hanson, D., MacGillivray, G., 10.1002/net.3230250203, Networks 25 (1995), 41-43. (1995) Zbl0820.05038MR1321108DOI10.1002/net.3230250203
  9. Fitzpatrick, S., Hartnell, B., 10.7151/dmgt.1063, Discuss. Math. Graph Theory 18 (1998), 63-72. (1998) Zbl0916.05061MR1646231DOI10.7151/dmgt.1063
  10. Goddard, W., Haynes, T. W., Henning, M. A., Merwe, L. C. van der, 10.1016/j.disc.2004.05.010, Discrete Math. 286 (2004), 255-261. (2004) MR2085130DOI10.1016/j.disc.2004.05.010
  11. Haynes, T. W., Hedetniemi, S. T., Slater, P. J., Fundamentals of Domination in Graphs, Marcel Dekker New York (1998). (1998) Zbl0890.05002MR1605684
  12. Haynes, T. W., Hedetniemi, S. T., Slater, P. J., Domination in Graphs. Advanced Topics, Marcel Dekker New York (1998). (1998) Zbl0883.00011MR1605685
  13. Haynes, T. W., Henning, M. A., Trees with large paired-domination number, Util. Math. 71 (2006), 3-12. (2006) Zbl1112.05078MR2278818
  14. Haynes, T. W., Slater, P. J., 10.1002/(SICI)1097-0037(199810)32:3<199::AID-NET4>3.0.CO;2-F, Networks 32 (1998), 199-206. (1998) Zbl0997.05074MR1645415DOI10.1002/(SICI)1097-0037(199810)32:3<199::AID-NET4>3.0.CO;2-F
  15. Haynes, T. W., Slater, P. J., Paired-domination and the paired-domatic number, Congr. Numerantium 109 (1995), 65-72. (1995) Zbl0904.05052MR1369295
  16. Henning, M. A., Trees with equal total domination and paired-domination numbers, Util. Math. 69 (2006), 207-218. (2006) Zbl1100.05070MR2212810
  17. Henning, M. A., 10.1007/s10878-006-9014-8, J. Comb. Optim. 13 (2007), 61-78. (2007) Zbl1108.05069MR2273264DOI10.1007/s10878-006-9014-8
  18. Henning, M. A., Plummer, M. D., 10.1007/s10878-005-4107-3, J. Comb. Optim. 10 (2005), 283-294. (2005) Zbl1122.05071MR2186747DOI10.1007/s10878-005-4107-3
  19. Proffitt, K. E., Haynes, T. W., Slater, P. J., Paired-domination in grid graphs, Congr. Numerantium 150 (2001), 161-172. (2001) Zbl0988.05067MR1887420
  20. Qiao, H., Kang, L., Cardei, M., Du, Ding-Zhu, 10.1023/A:1021338214295, J. Glob. Optim. 25 (2003), 43-54. (2003) Zbl1013.05055MR1969426DOI10.1023/A:1021338214295
  21. Sumner, D. P., 10.1016/0012-365X(90)90347-K, Discrete Math. 86 (1990), 33-46. (1990) Zbl0725.05049MR1088558DOI10.1016/0012-365X(90)90347-K
  22. Sumner, D. P., Blitch, P., 10.1016/0095-8956(83)90007-2, J. Comb. Theory Ser. B 34 (1983), 65-76. (1983) Zbl0512.05055MR0701172DOI10.1016/0095-8956(83)90007-2
  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. (1998) Zbl0891.05043MR1605701
  24. Wojcicka, E., 10.1002/jgt.3190140209, J. Graph Theory 14 (1990), 205-215. (1990) Zbl0702.05058MR1053604DOI10.1002/jgt.3190140209

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.