Roman-Type Domination on Convex and Chordal Bipartite Graphs: Algorithms and Hardness
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.15026
curl -X POST /api/v1/records/arxiv/2607.15026/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.15026/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'