Simultaneously dominating all spanning trees of a graph

DOI10.5614/EJGTA.2022.10.1.5MaRDI QIDQ5081207zbMATH OpenOpenAlexFDO

Authors Sebastian S. Johann, Manuel Streicher, Sven O. Krumke

Publication date 14 June 2022

Published in Electronic Journal of Graph Theory and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution-ShareAlike 4.0 International

Full work available at URL https://arxiv.org/abs/1810.12887

zbMATH Keywords

dominating setfactor dominationsimultaneous domination

Mathematics Subject Classification ID

Perfect graphs (05C17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85)

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.

Recommendations

• Bipartite Domination and Simultaneous Matroid Covers
• scientific article; zbMATH DE number 3918387
• On minimum dominating sets with minimum intersection
• Simultaneous domination in graphs
• scientific article; zbMATH DE number 1052836

Cites work

• A partial k-arboretum of graphs with bounded treewidth
• A survey of selected recent results on total domination in graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Factor domination in graphs
• Geometric algorithms and combinatorial optimization
• Graph theory
• Graph-theoretic concepts and algorithms
• scientific article; zbMATH DE number 3172309 (Why is no real title available?)
• scientific article; zbMATH DE number 4204392 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Independent domination in graphs: A survey and recent results
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• On simultaneous domination and mixed connectivity in graphs
• Simultaneous domination in graphs
• Simultaneous graph parameters: factor domination and factor total domination
• The strong perfect graph theorem
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)

Cited in

(2)

• Bipartite Domination and Simultaneous Matroid Covers
• Simultaneous domination in graphs

Describes a project that uses

Uses Software

• Algorithm 447

This page was built for publication: Simultaneously dominating all spanning trees of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5081207)