کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4650053 | 1342473 | 2009 | 10 صفحه PDF | دانلود رایگان |

A Roman domination function on a graph G=(V(G),E(G))G=(V(G),E(G)) is a function f:V(G)→{0,1,2}f:V(G)→{0,1,2} satisfying the condition that every vertex uu for which f(u)=0f(u)=0 is adjacent to at least one vertex vv for which f(v)=2f(v)=2. The weight of a Roman dominating function is the value f(V(G))=∑u∈V(G)f(u)f(V(G))=∑u∈V(G)f(u). The minimum weight of a Roman dominating function on a graph GG is called the Roman domination number of GG. Cockayne et al. [E. J. Cockayne et al. Roman domination in graphs, Discrete Mathematics 278 (2004) 11–22] showed that γ(G)≤γR(G)≤2γ(G)γ(G)≤γR(G)≤2γ(G) and defined a graph GG to be Roman if γR(G)=2γ(G)γR(G)=2γ(G). In this article, the authors gave several classes of Roman graphs: P3k,P3k+2,C3k,C3k+2P3k,P3k+2,C3k,C3k+2 for k≥1k≥1, Km,nKm,n for min{m,n}≠2{m,n}≠2, and any graph GG with γ(G)=1γ(G)=1; In this paper, we research on regular Roman graphs and prove that: (1) the circulant graphs C(n;{1,3})(n≥7,n⁄≡4(mod5)) and C(n;{1,2,…,k})(k≤⌊n2⌋), n⁄≡1n⁄≡1 (mod (2k+1)(2k+1)), (n≠2kn≠2k) are Roman graphs, (2) the generalized Petersen graphs P(n,2k+1)P(n,2k+1)(n≠4k+2,n≡0 (mod 4) and 0≤k≤⌊n2⌋), P(n,1)P(n,1) (n⁄≡2n⁄≡2 (mod 4)), P(n,3)P(n,3) (n≥7,n⁄≡3 (mod 4)) and P(11,3)P(11,3) are Roman graphs, and (3) the Cartesian product graphs C5m□C5n(m≥1,n≥1) are Roman graphs.
Journal: Discrete Mathematics - Volume 309, Issue 6, 6 April 2009, Pages 1528–1537