Id: arxiv/2607.08364 Url: https://arxiv.org/abs/2607.08364 Tags: math.CO Score: 0 Title: Roman domination on subclasses of bipartite graphs Domain: math.CO Source: arxiv Authors: Gautam K. Das, Sasmita Rout, Kamal Santra Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-07-09 Page: https://delphi.science/r/arxiv/2607.08364 The Roman Domination Problem (RDP) on a simple, finite, undirected graph \(G=(V,E)\) asks for a labeling function \(f:V\rightarrow\{0,1,2\}\) such that every vertex assigned value \(0\) is adjacent to at least one vertex assigned value \(2\). The objective is to minimize the total weight \(\sum_{v\in V} f(v)\), and this minimum value is called the Roman domination number of \(G\), denoted by \(γ_R(G)\). Since the RDP is NP-complete for bipartite graphs, a natural direction is to study its complexity on restricted subclasses of bipartite graphs. The problem remains NP-complete even under…