On the complexity of global Roman domination problem in graphs

Sangam Balchandar Reddy, Arun Kumar Das, Anjeneya Swami Kare, I. Vinod Reddy

arXivarxiv/2601.09167Jan 14, 2026math.COscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2601.09167
curl -X POST /api/v1/records/arxiv/2601.09167/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2601.09167/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'