Algorithmic aspects of outer-independent double Roman domination in graphs

DOI10.1142/S0129054124500059MaRDI QIDQ7032370zbMATH OpenFDO

Authors Amit Kumar Sharma, P. Venkata Subba Reddy, S. Arumugam, Jakkepalli Pavan Kumar

Publication date 5 February 2025

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

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

domination number NP-completeness outer-independent double Roman dominating set

Higher-order logic (03B16) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Review text

In this paper, the authors discuss a variation of the domination of a graph, namely outer-independent double Roman domination of a graph. An outer-independent double Roman dominating (OIDRD) function of a graph is a labeling from the vertices to the set \(\{0,1,2,3\}\) such that the following holds:\N\begin{itemize}\N\item vertices whose labels are \(0\) are adjacent to at least one vertex labeled with \(3\) or adjacent to at least two vertices labeled with \(2\),\N\item vertices whose labels are \(1\) are adjacent to at least one vertex labeled with \(2\) or \(3\),\N\item there are no two vertices labeled with \(0\) that are adjacent.\N\end{itemize}\NThe main problem is to determine the minimum sum of each vertice's labels among all OIDRD functions of a graph. Such a minimum number is then called an outer-independent double Roman domination number of the graph.\N\NThe authors prove that the problem of OIDRD in a particular family of graphs called split graphs is NP-complete. They also determine the OIDRD number of any threshold graph, given a number of its dominating vertices. This implies that the OIDRD number of any threshold graph can be computed in a linear time. In addition, the problem of OIDRD is expressible in counting monadic second-order logic, which implies a graph with its treewidth at most a constant is solvable in linear time. Furthermore, they show the existence of graphs whose OIDRD number is eight times their order. However, determining the domination number of such a particular graph is known to be NP-complete. This presents a gap between the `standard' domination problem and the OIDRD problem.\N\NSome knowledge is assumed for the readers to read this article. First, the definition of a split graph is not given in the article. Next, there are no examples of the OIDRD function of any graph. A bit of theoretical computer science is also needed since it is not described clearly what is NP-completeness and how to show that a particular problem is NP-complete. Lastly, the method of counting monadic second-order logic is rather not trivial. All these descriptions would make new readers harder to read the article if they are unfamiliar with each topic.\N\NThe proofs presented in the article, meanwhile, are somewhat straightforward. The NP-completeness of an OIDRD problem of split graphs is proved by translating such a problem to an exact three set cover (X3SC) problem and vice versa. The OIDRD number of a threshold graph is determined by presenting an OIDRD function with a certain sum of the labels and short explanations of why the sum cannot be less among all OIDRD functions of the graph. They show that the problem of OIDRD is expressible in counting monadic second-order logic by writing such an expression followed by a short description. Moreover, the gap between the `standard' domination problem and the OIDRD problem is shown by investigating an operation of a graph called an AS graph. Determining the properties of AS graphs does not seem to be hard.\N\NIn short, the article is interesting for readers who seek a variation of the domination of a graph. If one is already familiar with the concepts of graph theory (in particular split graph and the OIDRD problem), a bit of logic, and theoretical computer science, then they are able to read the results and the proofs of the article as the only source without problems. On the other hand, if the reader is not familiar with the assumed knowledge, then they should read the article alongside some references mentioned in the article.

Cites work

This page was built for publication: Algorithmic aspects of outer-independent double Roman domination in graphs

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