Algorithmic complexity of secure connected domination in graphs

DOI10.1016/J.AKCEJ.2019.08.012MaRDI QIDQ4956219zbMATH OpenOpenAlexFDO

Authors

Publication date 1 September 2021

Published in AKCE International Journal of Graphs and Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

dominationsecure connected dominationsecure dominationw[2-hard problem]

Mathematics Subject Classification ID

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

Abstract: Let $G=(V,E)$ be a simple, undirected and connected graph. A connected (total) dominating set $SsubseteqV$ is a secure connected (total) dominating set of $G$, if for each $uinVsetminusS$, there exists $vinS$ such that $uvinE$ and $(Ssetminuslbracevbrace)cuplbraceubrace$ is a connected (total) dominating set of $G$. The minimum cardinality of a secure connected (total) dominating set of $G$ denoted by $gamm{a}_{sc}(G)(gamm{a}_{st}(G))$, is called the secure connected (total) domination number of $G$. In this paper, we show that the decision problems corresponding to secure connected domination number and secure total domination number are NP-complete even when restricted to split graphs or bipartite graphs. The NP-complete reductions also show that these problems are w[2]-hard. We also prove that the secure connected domination problem is linear time solvable in block graphs and threshold graphs.

Recommendations

• Complexity issues of variants of secure domination in graphs
• Algorithmic aspects of secure connected domination in graphs
• Secure total domination in graphs: bounds and complexity
• On computing a minimum secure dominating set in block graphs
• The complexity of secure domination problem in graphs

Cites work

• Dominating sets for split and bipartite graphs
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2188604 (Why is no real title available?)
• Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
• Threshold graphs and related topics

Cited in

(14)

• On computing a minimum secure dominating set in block graphs
• A simple algorithm for secure domination in proper interval graphs
• Secure total domination in graphs: bounds and complexity
• The complexity of connected dominating sets and total dominating sets with specified induced subgraphs
• Algorithmic aspects of secure connected domination in graphs
• Algorithmic aspects of 2-secure domination in graphs
• Complexity issues of variants of secure domination in graphs
• Domination and its variants in split graphs \(-\text{P}\) versus NPC dichotomy
• Secure connected domination and secure total domination in unit disk graphs and rectangle graphs
• On computing secure domination of trees
• Complexity issues of perfect secure domination in graphs
• Algorithmic aspects of certified domination in graphs
• Complexity results on cosecure domination in graphs
• On the complexity of co-secure dominating set problem

This page was built for publication: Algorithmic complexity of secure connected domination in graphs

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