{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-09","reactions":{}}