کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4650053 1342473 2009 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Roman domination in regular graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Roman domination in regular graphs
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issue 6, 6 April 2009, Pages 1528–1537
نویسندگان
, , ,