Opuscula Math. 45, no. 6 (2025), 841-855
https://doi.org/10.7494/OpMath.2025.45.6.841

 
Opuscula Mathematica

A linear time algorithm to compute vertices that belong to all, some and no minimum dominating sets in a tree and its consequences

Radosław Ziemann
Paweł Żyliński

Abstract. We provide a linear time algorithm for determining the sets of vertices that belong to all, some and no minimum dominating sets of a tree, respectively, thus improving the quadratic time algorithm of Benecke and Mynhardt in 2008 [S. Benecke, C.M. Mynhardt, Trees with domination subdivision number one, Australas. J. Comb. 42 (2008), 201-209]. Some algorithmic consequences are also discussed.

Keywords: tree, domination, independence, vertex cover, dissociation, algorithm, linear time, dynamic programming.

Mathematics Subject Classification: 05C05, 05C69, 05C85.

Full text (pdf)

  1. 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. https://doi.org/10.1016/j.tcs.2007.09.013
  2. A. Babikir, M. Dettlaff, M.A. Henning, M. Lemańska, Independent domination subdivision in graphs, Graphs Combin. 37 (2021), 691-709. https://doi.org/10.1007/s00373-020-02269-3
  3. S. Benecke, C.M. Mynhardt, Trees with domination subdivision number one, Australas. J. Comb. 42 (2008), 201-209.
  4. C. Berge, Théorie des Graphes et ses Applications, Dunod, Paris, 1958.
  5. M. Blidia, R. Lounes, Vertices belonging to all or no minimum locating dominating set of trees, Opuscula Math. 29 (2009), 5-14. https://doi.org/10.7494/opmath.2009.29.1.5
  6. M. Blidia, M. Chellali, S. Khelifi, Vertices belonging to all or to no minimum double dominating sets in trees, AKCE Int. J. Gr. Comb. 2 (2005), 1-9.
  7. H.L. Bodlaender, Dynamic programming on graphs with bounded treewidth, Lect. Notes Comput. Sci. 317 (1988), 105-118. https://doi.org/10.1007/3-540-19488-6_110
  8. E. Boros, M.C. Golumbic, V.E. Levit, On the number of vertices belonging to all maximum stable sets of a graph, Discrete Appl. Math. 124 (2002), 17-25. https://doi.org/10.1016/s0166-218x(01)00327-4
  9. V. Bouquet, F. Delbot, Ch. Picouleau, On the vertices belonging to all, some, none minimum dominating set, Discrete Appl. Math. 288 (2021), 9-19. https://doi.org/10.1016/j.dam.2020.08.020
  10. B. Brešar, F. Kardoš, J. Katrenič, G. Semanišin, Minimum \(k\)-path vertex cover, Discrete Appl. Math. 159 (2011), 1189-1195. https://doi.org/10.1016/j.dam.2011.04.008
  11. T. Burton, D.P. Sumner, \(\gamma\)-excellent, critically dominated, end-dominated, and dot-critical trees are equivalent, Discrete Appl. Math. 307 (2007), 683-693. https://doi.org/10.1016/j.disc.2006.02.016
  12. K. Cameron, P. Hell, Independent packings in structured graphs, Math. Program. 105 (2006), 201-213. https://doi.org/10.1007/s10107-005-0649-5
  13. G.J. Chang, Algorithmic Aspects of Domination in Graphs, [in:] Handbook of Combinatorial Optimization, Springer, 2013, 221-282. https://doi.org/10.1007/978-1-4419-7997-1_26
  14. X.G. Chen, Vertices contained in all minimum paired-dominating sets of a tree, Czechoslov. Math. J. 57 (2007), 407-417. https://doi.org/10.1007/s10587-007-0069-1
  15. 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. https://doi.org/10.1016/s0012-365x(02)00447-8
  16. B. Courcelle, J.A. Makowsky, U. Rotics, Linear time solvable optimization problems on graphs on bounded clique width, Theory Comput. Syst. 33 (2000), 125-150. https://doi.org/10.1007/s002249910009
  17. S.E. Dreyfus, A.M. Law, The Art and Theory of Dynamic Programming, Academic Press, New York, 1977.
  18. M. Edwards, G. MacGillivray, S. Nasserasr, Reconfiguring minimum dominating sets: The \(\gamma\)-graph of a tree, Discuss. Math. Graph Theory 38 (2018), 703-716. https://doi.org/10.7151/dmgt.2044
  19. O. Favaron, On a conjecture of Fink and Jacobson concerning \(k\)-domination and \(k\)-dependence, J. Comb. Theory Ser. B 39 (1985), 101-102. https://doi.org/10.1016/0095-8956(85)90040-1
  20. G. Fricke, T. Haynes, S. Hedetniemi, S. Hedetniemi, R. Laskar, Excellent trees, Bull. Inst. Comb. Appl. 34 (2002), 27-38.
  21. G.H. Fricke, S.M. Hedetniemi, S.T. Hedetniemi, K.R. Hutson, \(\gamma\)-Graphs of graphs, Discuss. Math. Graph Theory 31 (2011), 517-531. https://doi.org/10.7151/dmgt.1562
  22. P. Golovach, P. Heggernes, M.M. Kanté, D. Kratsch, Y. Villanger, Minimal dominating sets in interval graphs and trees, Discrete Appl. Math. 216 (2017), 162-170. https://doi.org/10.1016/j.dam.2016.01.038
  23. G.H. Gunther, B. Hartnell, L. Markus, D. Rall, Graphs with unique minimum dominating sets, Congr. Numer. 101 (1994), 55-63.
  24. P.L. Hammer, P. Hansen, B. Simeone, Veritices belonging to all or to no maximum stable sets of a graph, SIAM J. Algebraic Discrete Methods 3 (1982), 511-522. https://doi.org/10.1137/0603052
  25. M.A. Henning, A.J. Marcon, Vertices contained in all or in no minimum semitotal dominating set of a tree, Discuss. Math. Graph Theory 36 (2016), 71-93. https://doi.org/10.7151/dmgt.1844
  26. M.A. Henning, A.J. Marcon, Vertices contained in all or in no minimum disjunctive dominating set of a tree, Util. Math. 105 (2017), 95-123.
  27. W.F. Klostermeyer, C.M. Mynhardt, A dynamic domination problem in trees, Trans. Comb. 4 (2015), 15-31.
  28. M. Krzywkowski, Trees having many minimal dominating sets, Inf. Process. Lett. 113 (2013), 276-279. https://doi.org/10.1016/j.ipl.2013.01.020
  29. M. Lemańska, P. Żyliński, Reconfiguring minimum dominating sets in trees, J. Graph Algorithms Appl. 24 (2020), 47-61. https://doi.org/10.7155/jgaa.00517
  30. V.E. Levit, E. Mandrescu, Combinatorial properties of the family of maximum stable sets of a graph, Discrete Appl. Math. 117 (2002), 149-161. https://doi.org/10.1016/s0166-218x(01)00183-4
  31. V.E. Levit, E. Mandrescu, Vertices belonging to all critical sets of a graph, SIAM J. Discrete Math. 26 (2012), 399-403. https://doi.org/10.1137/110823560
  32. N. Meddah, M. Blidia, S. Arumugam, Vertices contained in all or in no minimum \(k\)-dominating sets of a tree, AKCE Int. J. Graphs Comb. 11 (2014), 105-113.
  33. C.M. Mynhardt, Vertices contained in every minimum dominating set of a tree, J. Graph Theory 31 (1999), 155-265. https://doi.org/10.1002/(sici)1097-0118(199907)31:3<163::aid-jgt2>3.3.co;2-k
  34. C.M. Mynhardt H.C. Swart, E. Ungerer, Excellent trees and secure domination, Util. Math. 67 (2005), 255-267. https://doi.org/10.7151/dmgt.1405
  35. O. Ore, Theory of Graphs, American Mathematical Society Colloquium Publications vol. XXXVIII, AMS, Providence, 1962. https://doi.org/10.1090/coll/038
  36. Y. Orlovich, A. Dolgui, G. Finke, V. Gordon, F. Werner, The complexity of dissociation set problems in graphs, Discrete Appl. Math. 159 (2011), 1352-1366. https://doi.org/10.1016/j.dam.2011.04.023
  37. J. Petr, J. Portier, L. Versteegen, On the number of minimum dominating sets and total dominating sets in forests, J. Graph Theory 106 (2024), 976-993. https://doi.org/10.1002/jgt.23107
  38. G. Rote, The maximum number of minimal dominating sets in a tree, SODA (2019), 1201-1214. https://doi.org/10.1137/1.9781611975482.73
  39. V. Samodivkin, The bondage number of graphs: good and bad vertices, Discuss. Math. Graph Theory 28 (2008), 453-462. https://doi.org/10.7151/dmgt.1419
  40. J. Tu, L. Zhang, J. Du, R. Lang, Polynomial time recognition of vertices contained in all (or no) maximum dissociation sets of a tree, AIMS math. 7 (2022), 569-578. https://doi.org/10.3934/math.2022036
  41. M. Yannakakis, Node-deletion problems on bipartite graphs, SIAM J. Comput. 10 (1981), 310-327. https://doi.org/10.1137/0210022
  42. https://codeforces.com/contest/1092/problem/F (accessed: 13.10.2025) https://codeforces.com/contest/1092/problem/F
  43. https://www.geeksforgeeks.org/competitive-programming/dp-on-trees-for-competitive-programming/ (accessed 13.10.2025) https://www.geeksforgeeks.org/competitive-programming/dp-on-trees-for-competitive-programming/
  44. https://usaco.guide/gold/all-roots (accessed: 13.10.2025) https://usaco.guide/gold/all-roots
  • Communicated by Andrzej Żak.
  • Received: 2025-05-15.
  • Revised: 2025-10-10.
  • Accepted: 2025-11-05.
  • Published online: 2025-12-08.
Opuscula Mathematica - cover

Cite this article as:
Radosław Ziemann, Paweł Żyliński, A linear time algorithm to compute vertices that belong to all, some and no minimum dominating sets in a tree and its consequences, Opuscula Math. 45, no. 6 (2025), 841-855, https://doi.org/10.7494/OpMath.2025.45.6.841

Download this article's citation as:
a .bib file (BibTeX),
a .ris file (RefMan),
a .enw file (EndNote)
or export to RefWorks.

We advise that this website uses cookies to help us understand how the site is used. All data is anonymized. Recent versions of popular browsers provide users with control over cookies, allowing them to set their preferences to accept or reject all cookies or specific ones.