Document detail
ID
oai:arXiv.org:2407.03831
Topic
Mathematics - Combinatorics Computer Science - Discrete Mathem...Author
Paul, Kaustav Sharma, Ankit Pandey, ArtiCategory
Computer Science
Year
2024
listing date
7/17/2024
Keywords
dominating $f domination $ graphsAbstract
Given a graph $G=(V,E)$, a function $f:V\to \{0,1,2\}$ is said to be a \emph{Roman Dominating function} if for every $v\in V$ with $f(v)=0$, there exists a vertex $u\in N(v)$ such that $f(u)=2$.
A Roman Dominating function $f$ is said to be an \emph{Independent Roman Dominating function} (or IRDF), if $V_1\cup V_2$ forms an independent set, where $V_i=\{v\in V~\vert~f(v)=i\}$, for $i\in \{0,1,2\}$.
The total weight of $f$ is equal to $\sum_{v\in V} f(v)$, and is denoted as $w(f)$.
The \emph{Independent Roman Domination Number} of $G$, denoted by $i_R(G)$, is defined as min$\{w(f)~\vert~f$ is an IRDF of $G\}$.
For a given graph $G$, the problem of computing $i_R(G)$ is defined as the \emph{Minimum Independent Roman Domination problem}.
The problem is already known to be NP-hard for bipartite graphs.
In this paper, we further study the algorithmic complexity of the problem.
In this paper, we propose a polynomial-time algorithm to solve the Minimum Independent Roman Domination problem for distance-hereditary graphs, split graphs, and $P_4$-sparse graphs.
Paul, Kaustav,Sharma, Ankit,Pandey, Arti, 2024, Exploring Algorithmic Solutions for the Independent Roman Domination Problem in Graphs
