Research article Special Issues

Construction for trees without domination critical vertices

  • 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.

    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:

  • 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
  • Reader Comments
  • © 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)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(1911) PDF downloads(61) Cited by(1)

Article outline

Figures and Tables

Figures(5)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog