{"id":"arxiv/2601.09167","url":"https://arxiv.org/abs/2601.09167","tags":["math.CO","cs.CC","cs.DS"],"score":0,"title":"On the complexity of global Roman domination problem in graphs","domain":"math.CO","source":"arxiv","authors":["Sangam Balchandar Reddy","Arun Kumar Das","Anjeneya Swami Kare","I. Vinod Reddy"],"reviews":0,"subject":"math.CO","summary":"A Roman dominating function of a graph $G=(V,E)$ is a labeling $f: V \\rightarrow{} \\{0 ,1, 2\\}$ such that for each vertex $u \\in V$ with $f(u) = 0$, there exists a vertex $v \\in N(u)$ with $f(v) =2$. A Roman dominating function $f$ is a global Roman dominating function if it is a Roman dominating function for both $G$ and its complement $\\overline{G}$. The weight of $f$ is the sum of $f(u)$ over all the vertices $u \\in V$. The objective of Global Roman Domination problem is to find a global Roman dominating function with minimum weight. The objective of Global Roman Domination is to compute…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-01-14","reactions":{}}