{"id":"arxiv/2607.15026","url":"https://arxiv.org/abs/2607.15026","tags":["cs.DM","math.CO"],"score":0,"title":"Roman-Type Domination on Convex and Chordal Bipartite Graphs: Algorithms and Hardness","domain":"cs.DM","source":"arxiv","authors":["Gautam K. Das","Kamal Santra"],"reviews":0,"subject":"cs.DM","summary":"Roman domination and its variants form an important family of domination-type graph parameters motivated by protection, fault tolerance, and resource allocation. A Roman dominating function of a graph \\(G\\) is a function \\(f:V(G)\\rightarrow\\{0,1,2\\}\\) such that every vertex \\(v\\) with \\(f(v)=0\\) has a neighbour \\(u\\) with \\(f(u)=2\\). The weight of \\(f\\) is \\(w(f)=\\sum_{v\\in V(G)}f(v)\\), and the minimum weight of a Roman dominating function of \\(G\\) is the Roman domination number, denoted by \\(γ_R(G)\\). In this paper, we study four variants of Roman domination on two natural subclasses of…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-16","reactions":{}}