Perfect Roman Domination Number of Generalized Petersen Graphs P(n,2)
Symmetry · 20.11.2026 · 18 (11) · 1942
DOI: 10.3390/sym18111942 ↗Kurz gefasst
Fachartikel in der Zeitschrift Symmetry, online erschienen am 20.11.2026. Verfasst von Derya Doğan und 1 weiteren Autor:innen. Die Arbeit nennt 33 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
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.
Zitieren
APA
Doğan, D., & Toprakkaya, E. N. (2026). Perfect Roman Domination Number of Generalized Petersen Graphs P(n,2). Symmetry, 18(11), 1942. https://doi.org/10.3390/sym18111942
Vancouver
Doğan D, Toprakkaya EN. Perfect Roman Domination Number of Generalized Petersen Graphs P(n,2). Symmetry. 2026;18(11):1942. doi:10.3390/sym18111942
BibTeX
@article{Doan2026,
author = {Doğan, Derya and Toprakkaya, Emre Niyazi},
title = {Perfect Roman Domination Number of Generalized Petersen Graphs P(n,2)},
journal = {Symmetry},
year = {2026},
volume = {18},
number = {11},
pages = {1942},
doi = {10.3390/sym18111942}
}
EUVIMED