Answers are grounded in this paper and cite their sources.
Perfect Roman domination models protection schemes in which every unprotected site is defended by exactly one strong neighbor. A perfect Roman dominating function (PRDF) of a graph G is a function f:V(G)→{0,1,2} such that every vertex labeled 0 is adjacent to exactly one vertex labeled 2, and the perfect Roman domination number γRP(G) is the minimum weight of a PRDF of G. Computing γRP is NP-hard, and its value was unknown for the generalized Petersen graphs P(n,2), a benchmark family of cubic graphs with dihedral symmetry. We prove that γRP(P(n,2))=8q+cr for n=7q+r≥5 with 0≤r≤6, where (c0,…,c6)=(0,2,4,4,6,7,8). The upper bound follows from an explicit gluing of seven blocks, which gives a linear-time algorithm for a minimum PRDF. For the lower bound, the rotational symmetry turns all PRDFs into closed walks in a single transfer digraph with 2187 states; an integer potential certifies the minimum cycle mean 8/7, and a shortest-path computation modulo 7 gives the exact constants. Consequently, γRP(P(n,2)) exceeds the Roman domination number by at most one, and it equals 2n−2ϱ(P(n,2))−εn, where ϱ is the packing number and εn∈{0,1} equals 1 exactly when n≡5(mod7). Unlike a case analysis, this lower-bound proof rests on certificates that can be checked independently.
No takes yet. Share an insight, caveat, or question.
Durgun et al. (2026) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: