Cosecure domination: hardness results and algorithms

DOI10.1007/978-3-031-34347-6_21arXiv2302.13031OpenAlexW4379134728MaRDI QIDQ6182909FDOQ6182909

Authors: Kusum, Arti Pandey 

Publication date: 22 December 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: For a simple graph $G=(V,E)$ without any isolated vertex, a cosecure dominating set $D$ of $G$ satisfies the following two properties (i) $S$ is a dominating set of $G$, (ii) for every vertex $vinS$ there exists a vertex $uinVsetminusS$ such that $uvinE$ and $(Ssetminusv)cupu$ is a dominating set of $G$. The minimum cardinality of a cosecure dominating set of $G$ is called cosecure domination number of $G$ and is denoted by $gamm{a}_{cs}(G)$. The Minimum Cosecure Domination problem is to find a cosecure dominating set of a graph $G$ of cardinality $gamm{a}_{cs}(G)$. The decision version of the problem is known to be NP-complete for bipartite, planar, and split graphs. Also, it is known that the Minimum Cosecure Domination problem is efficiently solvable for proper interval graphs and cographs. In this paper, we work on various important graph classes in an effort to reduce the complexity gap of the Minimum Cosecure Domination problem. We show that the decision version of the problem remains NP-complete for circle graphs, doubly chordal graphs, chordal bipartite graphs, star-convex bipartite graphs and comb-convex bipartite graphs. On the positive side, we give an efficient algorithm to compute the cosecure domination number of chain graphs, which is an important subclass of bipartite graphs. In addition, we show that the problem is linear-time solvable for bounded tree-width graphs. Further, we prove that the computational complexity of this problem varies from the domination problem.

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

zbMATH Keywords

NP-completenessbipartite graphsdoubly chordal graphsbounded tree-width graphscosecure domination

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Discrete mathematics in relation to computer science (68Rxx)

Cites Work

• Reducibility among combinatorial problems
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The algorithmic use of hypertree structure and maximum neighbourhood orderings
• Linear-time certifying recognition algorithms and forbidden induced subgraphs
• Dominating sets for split and bipartite graphs
• Two Hardness Results on Feedback Vertex Sets
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• Title not available (Why is that?)
• On secure domination in graphs
• Secure domination and secure total domination in graphs
• Secure domination in cographs
• Co-secure and secure domination in graphs
• Topics in Domination in Graphs
• The complexity of secure domination problem in graphs
• Doubly chordal graphs, steiner trees, and connected domination
• Structures of domination in graphs
• The co-secure domination in proper interval graphs
• Correcting the algorithm for the secure domination number of cographs by Jha, Pradhan, and Banerjee
• Co-secure domination in Mycielski graphs
• Complexity results on cosecure domination in graphs

This page was built for publication: Cosecure domination: hardness results and algorithms

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