2024/07/04 by Kaustav Paul, Paul, Kaustav, Ankit Sharma +3
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2407.03831
openalex publication_date 2024/07/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a graph G=(V,E), a function f:V→ \0,1,2\ is said to be a Roman Dominating function if for every v∈ V with f(v)=0, there exists a vertex u∈ N(v) such that f(u)=2. A Roman Dominating function f is said to be an Independent Roman Dominating function (or IRDF), if V1∪ V2 forms an independent set, where Vi=\v∈ V~\vert~f(v)=i\, for i∈ \0,1,2\. The total weight of f is equal to ∑v∈ V f(v), and is denoted as w(f). The Independent Roman Domination Number of G, denoted by iR(G), is defined as min\w(f)~\vert~f is an IRDF of G\. For a given graph G, the problem of computing iR(G) is defined as the 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 P4-sparse graphs.