{"id":"arxiv/2609.19240","url":"https://arxiv.org/abs/2609.19240","tags":["cs.DM","math.CO"],"score":0,"title":"Roman Domination on Circular-Convex, Triad-Convex Bipartite Graphs and $P_4$-Tidy Graphs","domain":"cs.DM","source":"arxiv","authors":["Gautam K. Das","Kamal Santra"],"reviews":0,"subject":"cs.DM","summary":"The Roman Domination Problem (RDP) on a 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 a vertex assigned value \\(2\\). The objective is to minimize the total weight \\(\\sum_{v\\in V} f(v)\\); this minimum value is the Roman domination number of \\(G\\), denoted by \\(γ_R(G)\\). In this paper, we study RDP on graph classes motivated by convexity and induced-\\(P_4\\) structure. First, we consider circular-convex bipartite graphs, a natural superclass of convex bipartite graphs, where RDP is already known to be…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-21","reactions":{}}