错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On double Roman domination problem for several graph classes

  • Tatjana Zec,
  • Dragan Matić,
  • Marko Djukanović

摘要

A double Roman domination function (DRDF) on a graph \(G=(V,E)\) G = ( V , E ) is a mapping \(f :V\rightarrow \{0,1,2,3\}\) f : V { 0 , 1 , 2 , 3 } satisfying the conditions: (i) each vertex with 0 assigned is adjacent to a vertex with 3 assigned or at least two vertices with 2 assigned and (ii) each vertex with 1 assigned is adjacent to at least one vertex with 2 or 3 assigned. The weight of a DRDF f is defined as the sum \(\sum _{v\in V}f(v)\) v V f ( v ) . The minimum weight of a DRDF on a graph G is called the double Roman domination number (DRDN) of G. This study establishes the values on DRDN for several graph classes. The exact values of DRDN are proved for Kneser graphs \(K_{n,k},n\ge k(k+2)\) K n , k , n k ( k + 2 ) , Johnson graphs \(J_{n,2}\) J n , 2 , for a few classes of convex polytopes, and the flower snarks. Moreover, tight lower and upper bounds on SRDN are proved for some convex polytopes. For the generalized Petersen graphs \(P_{n,3}, n \not \equiv 0\,(\mathrm {mod\ 4})\) P n , 3 , n 0 ( mod 4 ) , we make a further improvement on the best known upper bound from the literature.