Construction for trees without domination critical vertices

Ying Wang; Fan Wang; Weisheng Zhao; Ying Wang; Fan Wang; Weisheng Zhao

doi:10.3934/math.2021621

AIMS Mathematics

2021, Volume 6, Issue 10: 10696-10706. doi: 10.3934/math.2021621

Previous Article Next Article

Research article Special Issues

Construction for trees without domination critical vertices

1.
Institute for Interdisciplinary Research, Jianghan University, Wuhan, Hubei 430056, China
2.
School of Sciences, Nanchang University, Nanchang, Jiangxi 330031, China

Received: 27 May 2021 Accepted: 08 July 2021 Published: 23 July 2021
MSC : 05C05, 05C69

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.
- tree,
- domination,
- critical vertex,
- fixed vertex,
- bad vertex
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

Related Papers:

Abstract

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.

References

[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

Reader Comments

Your name:*

Email:*
© 2021 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)