Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
paired-domination; vertex critical; bounds; diameter
paired-domination; vertex critical; bounds; diameter
Summary:
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.
References:
[1] Brigham, R. C., Chinn, P. Z., Dutton, R. D.: Vertex domination-critical graphs. Networks 18 (1988), 173-179. DOI 10.1002/net.3230180304 | MR 0953920 | Zbl 0658.05042
[2] Chellali, M., Haynes, T. W.: Trees with unique minimum paired-dominating sets. Ars Combin. 73 (2004), 3-12. MR 2098744 | Zbl 1082.05023
[3] Chellali, M., Haynes, T. W.: Total and paired-domination numbers of a tree. AKCE Int. J. Graphs Comb. 1 (2004), 69-75. MR 2120712 | Zbl 1066.05101
[4] Chellali, M., Haynes, T. W.: On paired and double domination in graphs. Util. Math. 67 (2005), 161-171. MR 2137931 | Zbl 1069.05058
[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 10.1007/s00373-004-0577-9 | MR 2108391 | Zbl 1054.05074
[7] Favaron, O., Sumner, D., Wojcicka, E.: The diameter of domination $k$-critical graphs. J. Graph Theory 18 (1994), 723-734. DOI 10.1002/jgt.3190180708 | MR 1297193 | Zbl 0807.05042
[8] Fulman, J., Hanson, D., MacGillivray, G.: Vertex domination-critical graphs. Networks 25 (1995), 41-43. DOI 10.1002/net.3230250203 | MR 1321108 | Zbl 0820.05038
[9] Fitzpatrick, S., Hartnell, B.: Paired-domination. Discuss. Math. Graph Theory 18 (1998), 63-72. DOI 10.7151/dmgt.1063 | MR 1646231 | Zbl 0916.05061
[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 10.1016/j.disc.2004.05.010 | MR 2085130
[11] Haynes, T. W., Hedetniemi, S. T., Slater, P. J.: Fundamentals of Domination in Graphs. Marcel Dekker New York (1998). MR 1605684 | Zbl 0890.05002
[12] Haynes, T. W., Hedetniemi, S. T., Slater, P. J.: Domination in Graphs. Advanced Topics. Marcel Dekker New York (1998). MR 1605685 | Zbl 0883.00011
[13] Haynes, T. W., Henning, M. A.: Trees with large paired-domination number. Util. Math. 71 (2006), 3-12. MR 2278818 | Zbl 1112.05078
[14] Haynes, T. W., Slater, P. J.: Paired-domination in graphs. Networks 32 (1998), 199-206. DOI 10.1002/(SICI)1097-0037(199810)32:3<199::AID-NET4>3.0.CO;2-F | MR 1645415 | Zbl 0997.05074
[15] Haynes, T. W., Slater, P. J.: Paired-domination and the paired-domatic number. Congr. Numerantium 109 (1995), 65-72. MR 1369295 | Zbl 0904.05052
[16] Henning, M. A.: Trees with equal total domination and paired-domination numbers. Util. Math. 69 (2006), 207-218. MR 2212810 | Zbl 1100.05070
[17] Henning, M. A.: Graphs with large paired-domination number. J. Comb. Optim. 13 (2007), 61-78. DOI 10.1007/s10878-006-9014-8 | MR 2273264 | Zbl 1108.05069
[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 10.1007/s10878-005-4107-3 | MR 2186747 | Zbl 1122.05071
[19] Proffitt, K. E., Haynes, T. W., Slater, P. J.: Paired-domination in grid graphs. Congr. Numerantium 150 (2001), 161-172. MR 1887420 | Zbl 0988.05067
[20] Qiao, H., Kang, L., Cardei, M., Du, Ding-Zhu: Paired-domination of trees. J. Glob. Optim. 25 (2003), 43-54. DOI 10.1023/A:1021338214295 | MR 1969426 | Zbl 1013.05055
[21] Sumner, D. P.: Critical concepts in domination. Discrete Math. 86 (1990), 33-46. DOI 10.1016/0012-365X(90)90347-K | MR 1088558 | Zbl 0725.05049
[22] Sumner, D. P., Blitch, P.: Domination critical graphs. J. Comb. Theory Ser. B 34 (1983), 65-76. DOI 10.1016/0095-8956(83)90007-2 | MR 0701172 | Zbl 0512.05055
[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 1605701 | Zbl 0891.05043
[24] Wojcicka, E.: Hamiltonian properties of domination-critical graphs. J. Graph Theory 14 (1990), 205-215. DOI 10.1002/jgt.3190140209 | MR 1053604 | Zbl 0702.05058
Search
Partner of
