Search Advanced

AIMS Mathematics

2022, Volume 7, Issue 1: 569-578. doi: 10.3934/math.2022036
Previous Article Next Article
Research article

Polynomial time recognition of vertices contained in all (or no) maximum dissociation sets of a tree

  • 1.
    School of Mathematics and Statistics, Beijing Technology and Business University, Beijing 100048, China
  • 2.
    Key Laboratory of Tibetan Information Processing and Machine Translation, Qinghai Province, XiNing 810008, China
  • 3.
    Key Laboratory of Tibetan Information Processing, Ministry of Education, XiNing 810008, China
  • 4.
    School of Mathematics and Statistics, Beijing Institute of Technology, Beijing 100081, China
  • 5.
    Department of Mathematics, Beijing University of Chemical Technology, Beijing 100029, China
  • 6.
    School of Electronics and Information Engineering, Beihang University, Beijing 100191, China
  • Received: 08 August 2021 Accepted: 07 October 2021 Published: 14 October 2021

  • MSC : 05C05, 05C69, 05C85

  • In a graph $ G $, a dissociation set is a subset of vertices which induces a subgraph with vertex degree at most 1. Finding a dissociation set of maximum cardinality in a graph is NP-hard even for bipartite graphs and is called the maximum dissociation set problem. The complexity of the maximum dissociation set problem in various sub-classes of graphs has been extensively studied in the literature. In this paper, we study the maximum dissociation problem from different perspectives and characterize the vertices belonging to all maximum dissociation sets, and no maximum dissociation set of a tree. We present a linear time recognition algorithm which can determine whether a given vertex in a tree is contained in all (or no) maximum dissociation sets of the tree. Thus for a tree with $ n $ vertices, we can find all vertices belonging to all (or no) maximum dissociation sets of the tree in $ O(n^2) $ time.

    Citation: Jianhua Tu, Lei Zhang, Junfeng Du, Rongling Lang. Polynomial time recognition of vertices contained in all (or no) maximum dissociation sets of a tree[J]. AIMS Mathematics, 2022, 7(1): 569-578. doi: 10.3934/math.2022036

    Related Papers:

  • In a graph $ G $, a dissociation set is a subset of vertices which induces a subgraph with vertex degree at most 1. Finding a dissociation set of maximum cardinality in a graph is NP-hard even for bipartite graphs and is called the maximum dissociation set problem. The complexity of the maximum dissociation set problem in various sub-classes of graphs has been extensively studied in the literature. In this paper, we study the maximum dissociation problem from different perspectives and characterize the vertices belonging to all maximum dissociation sets, and no maximum dissociation set of a tree. We present a linear time recognition algorithm which can determine whether a given vertex in a tree is contained in all (or no) maximum dissociation sets of the tree. Thus for a tree with $ n $ vertices, we can find all vertices belonging to all (or no) maximum dissociation sets of the tree in $ O(n^2) $ time.


    加载中


    [1] H. B. Acharya, T. Choi, R. A. Bazzi, M. G. Gouda, The $k$-observer problem in computer networks, Networking Sci., 1 (2012), 15–22.
    [2] V. E. Alekseev, R. Boliac, D. V. Korobitsyn, V. V. Lozin, NP-hard graph problems and boundary classes of graphs, Theor. Comput. Sci., 389 (2007), 219–236. doi: 10.1016/j.tcs.2007.09.013. doi: 10.1016/j.tcs.2007.09.013
    [3] M. Blidia, M. Chellali, S. Khelifi, Veritices belonging to all or to no minimum double dominating sets in trees, AKCE Int. J. Graphs Co., 2 (2005), 1–9.
    [4] R. Boliac, K. Cameron, V. V. Lozin, On computing the dissociation number and the induced matching number of bipartite graphs, Ars Comb., 72 (2004), 241–253.
    [5] J. A. Bondy, U. S. R. Murty, Graph Theory, Springer, New York, 2008. doi: 10.2307/3620535.
    [6] V. Bouquet, F. Delbot, C. Picouleau, On the vertices belonging to all, some, none minimum dominating set, Discrete Appl. Math., 288 (2021), 9–19. doi: 10.1016/j.dam.2020.08.020. doi: 10.1016/j.dam.2020.08.020
    [7] B. Brešar, F. Kardoš, J. Katrenič, G. Semanišin, Minimum $k$-path vertex cover, Discrete Appl. Math., 159 (2011), 1189–1195. doi: 10.1016/j.dam.2011.04.008. doi: 10.1016/j.dam.2011.04.008
    [8] K. Cameron, P. Hell, Independent packings in structured graphs, Math. Program., 105 (2006), 201–213. doi: 10.1007/s10107-005-0649-5. doi: 10.1007/s10107-005-0649-5
    [9] M. S. Chang, L. H. Chen, L. J. Hung, Y. Z. Liu, P. Rossmanith, S. Sikdar, An $O^*(1.4658^n)$-time exact algorithm for the maximum bounded-degree-1 set problem, In: Proceedings of the 31st Workshop on Combinatorial Mathematics and Computation Theory, 2014, 9–18.
    [10] E. J. Cockayne, M. A. Henning, C. M. Mynhardt, Vertices contained in all or in no minimum total dominating set of a tree, Discrete Math., 260 (2003), 37–44. doi: 10.1016/S0012-365X(02)00447-8. doi: 10.1016/S0012-365X(02)00447-8
    [11] P. L. Hammer, P. Hansen, B. Simeone, Vertices belonging to all or to no maximum stable sets of a graph, SIAM J. Algebraic Discrete Math., 3 (1982), 511–522. doi: 10.1137/0603052. doi: 10.1137/0603052
    [12] F. Havet, R. J. Kang, J. S. Sereni, Improper colouring of unit disk graphs, Networks, 54 (2009), 150–164. doi: 10.1002/net. doi: 10.1002/net
    [13] F. Kardoš, J. Katrenič, I. Schiermeyer, On computing the minium 3-path vertex cover and dissociation number of graphs, Theor. Comput. Sci., 412 (2011), 7009–7017. doi: 10.1016/j.tcs.2011.09.009. doi: 10.1016/j.tcs.2011.09.009
    [14] J. Katrenič, A faster FPT algorithm for 3-path vertex cover, Inform. Process. Lett., 116 (2016), 273–278. doi: 10.1016/j.ipl.2015.12.002. doi: 10.1016/j.ipl.2015.12.002
    [15] 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. doi: 10.1002/(SICI)1097-0118(199907)31:3<163::AID-JGT2>3.0.CO;2-T
    [16] Y. Orlovich, A. Dolguib, G. Finkec, V. Gordond, F. Wernere, The complexity of dissociation set problems in graphs, Discrete Appl. Math., 159 (2011), 1352–1366. doi: 10.1016/j.dam.2011.04.023. doi: 10.1016/j.dam.2011.04.023
    [17] C. H. Papadimitriou, M. Yannakakis, The complexity of restricted spanning tree problems, J. Assoc. Comput. Mach., 29 (1982), 285–309. doi: 10.1145/322307.322309. doi: 10.1145/322307.322309
    [18] J. H. Tu, Z. P. Zhang, Y. T. Shi, The maximum number of maximum dissociation sets in trees, J. Graph Theory, 96 (2021), 472–489. doi: 10.1002/jgt.22627. doi: 10.1002/jgt.22627
    [19] J. H. Tu, W. L. Zhou, A primal-dual approximation algorithm for the vertex cover $P_3$ problem, Theor. Comput. Sci., 412 (2011), 7044–7048. doi: 10.1016/j.tcs.2011.09.013. doi: 10.1016/j.tcs.2011.09.013
    [20] M. Xiao, S. Kou, Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems, Theor. Comput. Sci., 657 (2017), 86–97. doi: 10.1016/j.tcs.2016.04.043. doi: 10.1016/j.tcs.2016.04.043
    [21] M. Yannakakis, Node-deletion problems on bipartite graphs, SIAM J. Comput., 10 (1981), 310–327. doi: 10.1137/0210022. doi: 10.1137/0210022
  • Reader Comments
  • © 2022 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搜索
AIMS Mathematics
1.8 3.4

Metrics

Article views(1950) PDF downloads(68) Cited by(0)

Preview PDF
Download XML
Export Citation
Article outline

Figures and Tables

Tables(1)

Other Articles By Authors

Related pages

Tools

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog