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

DOI10.1016/j.ipl.2012.09.002zbMath1259.68084MaRDI 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 complexity; combinatorial problems; total domination; connected domination; dominating subgraphs

Mathematics Subject Classification ID

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Related Items

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

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