Algorithmic aspects of k-part degree restricted domination in graphs

DOI10.1142/S1793830920500573MaRDI QIDQ5858166zbMATH OpenOpenAlexFDO

Authors S. S. Kamath, A. Senthil Thilak, Rashmi

Publication date 9 April 2021

Published in Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s1793830920500573

zbMATH Keywords

\(k\)-part degree restricted dominating set\textsf{NP}-completenessdominating setvertex cover

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Relation between k-DRD and dominating set
• Algorithmic aspects of the \(k\)-domination problem in graphs
• Bounds on k-part degree restricted domination number of a graph
• The algorithmic complexity of \(k\)-domatic partition of graphs
• Algorithmic aspects of secure connected domination in graphs

Cites work

• Cutting down recursive trees
• Dominating sets for split and bipartite graphs
• Dominating Sets in Chordal Graphs
• Graph Classes: A Survey
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• Relation between k-DRD and dominating set
• The complexity of domination problems in circle graphs
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs

Cited in

(2)

• Relation between k-DRD and dominating set
• k-Efficient domination: Algorithmic perspective

This page was built for publication: Algorithmic aspects of \(k\)-part degree restricted domination in graphs

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