| Title:
|
The diameter of paired-domination vertex critical graphs (English) |
| Author:
|
Henning, Michael A. |
| Author:
|
Mynhardt, Christina M. |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
58 |
| Issue:
|
4 |
| Year:
|
2008 |
| Pages:
|
887-897 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
paired-domination |
| Keyword:
|
vertex critical |
| Keyword:
|
bounds |
| Keyword:
|
diameter |
| MSC:
|
05C12 |
| MSC:
|
05C35 |
| MSC:
|
05C69 |
| idZBL:
|
Zbl 1174.05093 |
| idMR:
|
MR2471154 |
| . |
| Date available:
|
2010-07-21T08:03:41Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/140428 |
| . |
| Reference:
|
[1] Brigham, R. C., Chinn, P. Z., Dutton, R. D.: Vertex domination-critical graphs.Networks 18 (1988), 173-179. Zbl 0658.05042, MR 0953920, 10.1002/net.3230180304 |
| Reference:
|
[2] Chellali, M., Haynes, T. W.: Trees with unique minimum paired-dominating sets.Ars Combin. 73 (2004), 3-12. Zbl 1082.05023, MR 2098744 |
| Reference:
|
[3] Chellali, M., Haynes, T. W.: Total and paired-domination numbers of a tree.AKCE Int. J. Graphs Comb. 1 (2004), 69-75. Zbl 1066.05101, MR 2120712 |
| Reference:
|
[4] Chellali, M., Haynes, T. W.: On paired and double domination in graphs.Util. Math. 67 (2005), 161-171. Zbl 1069.05058, MR 2137931 |
| Reference:
|
[5] Edwards, M.: Criticality concepts for paired domination in graphs.Master Thesis University of Victoria (2006). |
| Reference:
|
[6] Favaron, O., Henning, M. A.: Paired domination in claw-free cubic graphs.Graphs Comb. 20 (2004), 447-456. Zbl 1054.05074, MR 2108391, 10.1007/s00373-004-0577-9 |
| Reference:
|
[7] Favaron, O., Sumner, D., Wojcicka, E.: The diameter of domination $k$-critical graphs.J. Graph Theory 18 (1994), 723-734. Zbl 0807.05042, MR 1297193, 10.1002/jgt.3190180708 |
| Reference:
|
[8] Fulman, J., Hanson, D., MacGillivray, G.: Vertex domination-critical graphs.Networks 25 (1995), 41-43. Zbl 0820.05038, MR 1321108, 10.1002/net.3230250203 |
| Reference:
|
[9] Fitzpatrick, S., Hartnell, B.: Paired-domination.Discuss. Math. Graph Theory 18 (1998), 63-72. Zbl 0916.05061, MR 1646231, 10.7151/dmgt.1063 |
| Reference:
|
[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. MR 2085130, 10.1016/j.disc.2004.05.010 |
| Reference:
|
[11] Haynes, T. W., Hedetniemi, S. T., Slater, P. J.: Fundamentals of Domination in Graphs.Marcel Dekker New York (1998). Zbl 0890.05002, MR 1605684 |
| Reference:
|
[12] Haynes, T. W., Hedetniemi, S. T., Slater, P. J.: Domination in Graphs. Advanced Topics.Marcel Dekker New York (1998). Zbl 0883.00011, MR 1605685 |
| Reference:
|
[13] Haynes, T. W., Henning, M. A.: Trees with large paired-domination number.Util. Math. 71 (2006), 3-12. Zbl 1112.05078, MR 2278818 |
| Reference:
|
[14] Haynes, T. W., Slater, P. J.: Paired-domination in graphs.Networks 32 (1998), 199-206. Zbl 0997.05074, MR 1645415, 10.1002/(SICI)1097-0037(199810)32:3<199::AID-NET4>3.0.CO;2-F |
| Reference:
|
[15] Haynes, T. W., Slater, P. J.: Paired-domination and the paired-domatic number.Congr. Numerantium 109 (1995), 65-72. Zbl 0904.05052, MR 1369295 |
| Reference:
|
[16] Henning, M. A.: Trees with equal total domination and paired-domination numbers.Util. Math. 69 (2006), 207-218. Zbl 1100.05070, MR 2212810 |
| Reference:
|
[17] Henning, M. A.: Graphs with large paired-domination number.J. Comb. Optim. 13 (2007), 61-78. Zbl 1108.05069, MR 2273264, 10.1007/s10878-006-9014-8 |
| Reference:
|
[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. Zbl 1122.05071, MR 2186747, 10.1007/s10878-005-4107-3 |
| Reference:
|
[19] Proffitt, K. E., Haynes, T. W., Slater, P. J.: Paired-domination in grid graphs.Congr. Numerantium 150 (2001), 161-172. Zbl 0988.05067, MR 1887420 |
| Reference:
|
[20] Qiao, H., Kang, L., Cardei, M., Du, Ding-Zhu: Paired-domination of trees.J. Glob. Optim. 25 (2003), 43-54. Zbl 1013.05055, MR 1969426, 10.1023/A:1021338214295 |
| Reference:
|
[21] Sumner, D. P.: Critical concepts in domination.Discrete Math. 86 (1990), 33-46. Zbl 0725.05049, MR 1088558, 10.1016/0012-365X(90)90347-K |
| Reference:
|
[22] Sumner, D. P., Blitch, P.: Domination critical graphs.J. Comb. Theory Ser. B 34 (1983), 65-76. Zbl 0512.05055, MR 0701172, 10.1016/0095-8956(83)90007-2 |
| Reference:
|
[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. Zbl 0891.05043, MR 1605701 |
| Reference:
|
[24] Wojcicka, E.: Hamiltonian properties of domination-critical graphs.J. Graph Theory 14 (1990), 205-215. Zbl 0702.05058, MR 1053604, 10.1002/jgt.3190140209 |
| . |
