Secure total domination in graphs: bounds and complexity

DOI10.1016/J.DAM.2016.08.018MaRDI QIDQ1786876zbMATH OpenOpenAlexFDO

Authors Oleg Duginov

Publication date 25 September 2018

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2016.08.018

zbMATH Keywords

computational complexityapproximation algorithmssecure total dominating setsecure total domination number

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Secure total domination in chain graphs and cographs
• On secure domination in graphs
• Secure domination and secure total domination in graphs
• The complexity of secure domination problem in graphs
• Algorithmic complexity of secure connected domination in graphs

Cites work

• scientific article; zbMATH DE number 1330032 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• scientific article; zbMATH DE number 1550912 (Why is no real title available?)
• scientific article; zbMATH DE number 2188604 (Why is no real title available?)
• A survey of selected recent results on total domination in graphs
• Approximation hardness of dominating set problems in bounded degree graphs
• Clustering and domination in perfect graphs
• Dominating sets for split and bipartite graphs
• Domination in the corona and join of graphs
• Eigensharp Graphs: Decomposition into Complete Bipartite Subgraphs
• Face covers and the genus problem for apex graphs
• Graphs of separability at most 2
• Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs
• Secure domination and secure total domination in graphs
• Secure total domination in graphs
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• Total domination in graphs

Cited in

(23)

• An algorithm for the secure total domination problem in proper interval graphs
• Eternal and Secure Domination in Graphs
• Secure domination of some graph operators
• On secure domination in graphs
• Algorithmic aspects of 2-secure domination in graphs
• Algorithmic aspects of secure connected domination in graphs
• Algorithmic complexity of secure connected domination in graphs
• Differentiating-total domination: approximation and hardness results
• Secure total domination number in maximal outerplanar graphs
• Secure total domination in graphs
• From (secure) \(w\)-domination in graphs to protection of lexicographic product graphs
• Total protection of lexicographic product graphs
• On computing secure domination of trees
• Secure Italian domination in graphs
• On the secure domination numbers of maximal outerplanar graphs
• Secure domination and secure total domination in graphs
• On the complexity of strong and weak total domination in graphs
• Complexity issues of perfect secure domination in graphs
• Secure connected domination and secure total domination in unit disk graphs and rectangle graphs
• The complexity of secure domination problem in graphs
• Secure total domination in chain graphs and cographs
• Algorithmic results in secure total dominating sets on graphs
• Graphs with diameter 2 and large total domination number

This page was built for publication: Secure total domination in graphs: bounds and complexity

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