The complexity of connected dominating sets and total dominating sets with specified induced subgraphs

DOI10.1016/j.ipl.2012.09.002zbMath1259.68084OpenAlexW1987967894MaRDI QIDQ1941700

Oliver Schaudt, Rainer Schrader

Publication date: 21 March 2013

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2012.09.002

zbMATH Keywords

computational complexitycombinatorial problemstotal dominationconnected dominationdominating subgraphs

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

A unified greedy approximation for several dominating set problems, On dominating sets whose induced subgraphs have a bounded diameter, On a class of graphs between threshold and total domishold graphs, An efficient algorithm for distance total domination in block graphs, Connected Domination, Linear separation of connected dominating sets in graphs, Acyclic total dominating sets in cubic graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on connected dominating sets of distance-hereditary graphs
• Maximal cliques in \(\{P_{2} \cup P_{3},C_{4}\}\)-free graphs
• Complete description of forbidden subgraphs in the structural domination problem
• Threshold dominating cliques in random graphs and interval routing
• Dominating cliques in \(P_ 5\)-free graphs
• Acyclic domination
• Restricted total domination in graphs
• An exact algorithm for the minimum dominating clique problem
• Dominating and large induced trees in regular graphs
• Hereditary Domination in Graphs: Characterization with Forbidden Induced Subgraphs
• Planar 3DM is NP-complete
• Graph Classes: A Survey
• Hereditary domination and independence parameters
• Dominating cliques in graphs