2011/03/12 by Haoli Wang, Wang, Haoli, Xirong Xu +5
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1103.2419
openalex publication_date 2011/03/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A Roman domination function on a graph G=(V, E) is a function f:V(G)→\0,1,2\ satisfying the condition that every vertex u with f(u)=0 is adjacent to at least one vertex v with f(v)=2. The weight of a Roman domination function f is the value f(V(G))=∑u∈ V(G)f(u). The minimum weight of a Roman dominating function on a graph G is called the Roman domination number of G, denoted by γR(G). In this paper, we study the \it Roman domination number of generalized Petersen graphs P(n,2) and prove that γR(P(n,2)) = \lceil (8n)/(7)\rceil (n ≥ 5).