Denote by $ \gamma(G) $ the domination number of graph $ G $. A vertex $ v $ of a graph $ G $ is called fixed if $ v $ belongs to every minimum dominating set of $ G $, and bad if $ v $ does not belong to any minimum dominating set of $ G $. A vertex $ v $ of $ G $ is called critical if $ \gamma(G-v) < \gamma(G) $. By using these notations of vertices, we give a construction for trees that does not contain critical vertices.
Citation: Ying Wang, Fan Wang, Weisheng Zhao. Construction for trees without domination critical vertices[J]. AIMS Mathematics, 2021, 6(10): 10696-10706. doi: 10.3934/math.2021621
Denote by $ \gamma(G) $ the domination number of graph $ G $. A vertex $ v $ of a graph $ G $ is called fixed if $ v $ belongs to every minimum dominating set of $ G $, and bad if $ v $ does not belong to any minimum dominating set of $ G $. A vertex $ v $ of $ G $ is called critical if $ \gamma(G-v) < \gamma(G) $. By using these notations of vertices, we give a construction for trees that does not contain critical vertices.
[1] | N. Ananchuen, M. D. Plummer, Matchings in 3-vertex-critical graphs: The even case, Networks, 45 (2005), 210–213. doi: 10.1002/net.20065 |
[2] | N. Ananchuen, M. D. Plummer, Matchings in 3-vertex-critical graphs: The odd case, Discrete Math., 307 (2007), 1651–1658. doi: 10.1016/j.disc.2006.09.015 |
[3] | D. Bauer, F. Harary, J. Nieminen, C. L. Suffel, Domination alteration sets in graphs, Discrete Math., 47 (1983), 153–161. doi: 10.1016/0012-365X(83)90085-7 |
[4] | R. C. Brigham, P. Z. Chinn, R. D. Dutton, Vertex domination-critical graphs, Networks, 18 (1988), 173–179. doi: 10.1002/net.3230180304 |
[5] | C. H. Cruz, M. Lemańska, R. Zuazua, A characterization of trees having a minimum vertex cover which is also a minimum total dominating set, Australas. J. Comb., 73 (2019), 334–345. |
[6] | P. Dankelmann, J. H. Hattingh, M. A. Henning, H. C. Swart, Trees with equal domination and restrained domination numbers, J. Global Optim., 34 (2006), 597–607. doi: 10.1007/s10898-005-8565-z |
[7] | M. Dorfling, W. Goddard, M. A. Henning, C. M. Mynhardt, Construction of trees and graphs with equal domination parameters, Discrete Math., 306 (2006), 2647–2654. doi: 10.1016/j.disc.2006.04.031 |
[8] | M. R. Garey, D. S. Johnson, Computers and intractability: A guide to the theory of NP-completeness, San Francisco, Calif, USA: W. H. Freeman and Company, 1979. |
[9] | G. Gunther, B. Hartnell, L. R. Markus, D. F. Rall, Graphs with unique minimum dominating sets, Congr. Numer., 101 (1994), 55–63. |
[10] | J. H. Hattingh, M. A. Henning, Characterizations of trees with equal domination parameters, J. Graph Theory, 34 (2000), 142–153. doi: 10.1002/1097-0118(200006)34:2<142::AID-JGT3>3.0.CO;2-V |
[11] | T. W. Haynes, S. T. Hedetniemi, M. A. Henning, Structures of domination in graphs, Springer Nature Switzerland AG, 2020. |
[12] | T. W. Haynes, S. T. Hedetniemi, M. A. Henning, Topics in domination in graphs, Springer Nature Switzerland AG, 2020. |
[13] | T. W. Haynes, S. T. Hedetniemi, P. J. Slater, Fundamentals of domination in graphs, New York: Marcel Dekker, 1998. |
[14] | T. W. Haynes, S. T. Hedetniemi, P. J. Slater, Domination in graphs: Advanced topics, New York: Marcel Dekker, 1998. |
[15] | T. W. Haynes, M. A. Henning, Trees with two disjoint minimum independent dominating sets, Discrete Math., 304 (2005), 69–78. doi: 10.1016/j.disc.2005.09.012 |
[16] | T. W. Haynes, M. A. Henning, Changing and unchanging domination: A classification, Discrete Math., 272 (2003), 65–79. doi: 10.1016/S0012-365X(03)00185-7 |
[17] | M. A. Henning, A. Yeo, Total domination in graphs, New York: Heidelberg Dordrecht London Springer, 2013. |
[18] | M. A. Henning, S. A Marcon, A constructive characterization of trees with equal total domination and disjunctive domination numbers, Quaest. Math., 39 (2016), 531–543. doi: 10.2989/16073606.2015.1096860 |
[19] | A. P. Kazemi, Every $K_{1, 7}$ and $K_{1, 3}$-free, 3-vertex critical graph of even order has a perfect matching, J. Discrete Math. Sci. Cryptogr., 13 (2010), 583–591. doi: 10.1080/09720529.2010.10698316 |
[20] | A. C. Martínez, A. M. Arias, M. M. Castillo, A characterization relating domination, semitotal domination and total Roman domination in trees, Commun. Comb. Optim., 6 (2021), 197–209. |
[21] | A. C. Martínez, I. G. Yero, A characterization of trees with equal Roman $\{2\}$-domination and Roman domination numbers, Commun. Comb. Optim., 4 (2019), 95–107. |
[22] | C. M. Mynhardt, Vertices contained in every minimum dominating set of a tree, J. Graph Theory, 31 (1999), 163–177. doi: 10.1002/(SICI)1097-0118(199907)31:3<163::AID-JGT2>3.0.CO;2-T |
[23] | V. Samodivkin, Domination in graphs, God. Univ. Arkhit. Stroit. Geod. Sofiya, Svitk II, Mat. Mekh., 39 (1996-1997), 111–135. |
[24] | V. Samodivkin, Changing and unchanging of the domination number of a graph, Discrete Math., 308 (2008), 5015–5025. doi: 10.1016/j.disc.2007.08.088 |
[25] | V. Samodivkin, The bondage number of graphs: Good and bad vertices, Discuss. Math. Graph Theory, 28 (2008), 453–462. doi: 10.7151/dmgt.1419 |
[26] | E. Shan, L. Kang, M. A. Henning, A characterization of trees with equal total domination and paired-domination numbers, Australas. J. Comb., 30 (2004), 31–39. |
[27] | D. Sumner, P. Blitch, Domination critical graphs, J. Comb. Theory Ser. B, 34 (1983), 65–76. doi: 10.1016/0095-8956(83)90007-2 |
[28] | U. Teschner, New results about the bondage number of a graph, Discrete Math., 171 (1997), 249–259. doi: 10.1016/S0012-365X(96)00007-6 |
[29] | T. Wang, Q. L. Yu, Factor-critical property in $3$-dominating-critical graphs, Discrete Math., 309 (2009), 1079–1083. doi: 10.1016/j.disc.2007.11.062 |
[30] | T. Wang, Q. L. Yu, A conjecture on $k$-factor-critical and $3$-$\gamma$-critical graphs, Sci. China Math., 53 (2010), 1385–1391. doi: 10.1007/s11425-009-0192-6 |
[31] | W. S. Zhao, X. L. Gao, H. P. Zhang, Construction for trees without vertices contained in all minimum dominating sets, Ars Combinatoria, 138 (2018), 3–16. |
[32] | W. S. Zhao, H. P. Zhang, Upper bounds on the bondage number of the strong product of a graph and a tree, Int. J. Comput. Math., 95 (2017), 511–527. |
[33] | W. S. Zhao, F. Wang, X. L. Gao, H. Li, Bondage number of the strong product of two trees, Discrete Appl. Math., 230 (2017), 133–145. doi: 10.1016/j.dam.2017.06.019 |
[34] | W. S. Zhao, F. Wang, H. P. Zhang, Construction for trees with unique minimum dominating sets, Int. J. Comput. Math.: Comput. Syst. Theory, 3 (2018), 204–213. doi: 10.1080/23799927.2018.1531930 |