Simultaneously dominating all spanning trees of a graph
Abstract
We investigate the problem of simultaneously dominating all spanning trees of a given graph. We prove that on 2-connected graphs, a subset of the vertices dominates all spanning trees of the graph if and only if it is a vertex cover. Using this fact we present an exact algorithm that finds a simultaneous dominating set of minimum size using an oracle for finding a minimum vertex cover. The algorithm can be implemented to run in polynomial time on several graph classes, such as bipartite or chordal graphs. We prove that there is no polynomial time algorithm that finds a minimum simultaneous dominating set on perfect graphs unless P=NP. Finally, we provide a 2-approximation algorithm for finding a minimum simultaneous dominating set.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2022.10.1.5
References
S. Arnborg and A. Proskurowski, Linear time algorithms for NP-hard problems restricted to partial k-trees. Discrete Applied Mathematics 23(1):11–24, 1989. doi:10.1016/0166-218X(89)90031-0.
R.C. Brigham and R D. Dutton, Factor domination in graphs, Discrete Mathematics 86(1):127–136, 1990. doi:10.1016/0012-365X(90)90355-L.
C. Berge. Théorie des Graphes et ses Applications, Collection universitaire de mathématiques, Dunod, 1958. doi:10.2307/2311389.
H.L. Bodlaender, A partial k-arboretum of graphs with bounded treewidth, Theoretical Computer Science 209(1):1–45, 1998. doi:10.1016/S0304-3975(97)00228-4.
Y. Caro and M.A. Henning, Simultaneous domination in graphs, Graphs and Combinatorics 30(6):1399–1416, 2014. doi:10.1007/s00373-013-1353-5.
M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas. The strong perfect graph theorem, Annals Of Mathematics 164:51–229, 2006. doi:10.4007/annals.2006.164.51.
P. Dankelmann, M.A. Henning, W. Goddard, and R. Laskar. Simultaneous graph parameters: Factor domination and factor total domination, Discrete Mathematics 306(18):2229–2233, 2006. doi:10.1016/j.disc.2006.04.017.
R. Diestel, Graph Theory: 5th edition. Springer Graduate Texts in Mathematics. Springer, 2017. doi:10.1007/978-3-662-53622-3.
W. Goddard and M.A. Henning. Independent domination in graphs: A survey and recent results, Discrete Mathematics 313(7):839–854, 2013. doi:10.1016/j.disc.2012.11.031.
M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., 1979. doi:10.1137/1024022.
M. Grötschel, Lovász, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, volume 2 of Algorithms and Combinatorics. Springer, 1988. doi:10.1007/978-3-642-78240-4.
M.A. Henning. A survey of selected recent results on total domination in graphs, Discrete Mathematics 309(1):32–63, 2009. doi:10.1016/j.disc.2007.12.044.
J.E. Hopcroft and R.E. Tarjan. Algorithm 447: Efficient algorithms for graph manipulation, Communications of the ACM 16(6):372–378, 1973. doi:10.1145/362248.362272.
S. Johann, On Simultaneous Domination and Mixed Connectivity in Graphs. PhD thesis, TU Kaiserslautern, 2021.
S.O. Krumke and H. Noltemeier,Graphentheoretische Konzepte und Algorithmen, Leitfäden der Informatik, Vieweg+Teubner, 2012. doi:https://doi.org/10.1007/978-3-8348-2264-2.
S. Khot and O. Regev. Vertex cover might be hard to approximate to within 2 − ε, Journal of Computer and System Sciences 74(3):335–349, 2008. doi:10.1016/j.jcss.2007.06.019.
Ø. Ore. Theory of Graphs, AMS colloquium publications. AMS, 1962. doi:10.1090/coll/038.
E. Sampathkumar, The global domination number of a graph, J. Math. Phys. Sci. 23(5):377–385, 1989.
A. Schrijver. Combinatorial Optimization - Polyhedra and Efficiency, Springer, 2003.
M. Streicher. Uncertainty in Discrete Optimization: Connectivity and Covering, PhD thesis, TU Kaiserslautern, 2021.
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.