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

Disprove of a conjecture on the double Roman domination number

  • Z. Shao,
  • R. Khoeilar,
  • H. Karami,
  • M. Chellali,
  • S. M. Sheikholeslami

摘要

A double Roman dominating function (DRDF) on a graph \(G=(V,E)\) G = ( V , E ) is a function \(f:V\rightarrow \{0,1,2,3\}\) f : V { 0 , 1 , 2 , 3 } having the property that if \(f(v)=0\) f ( v ) = 0 , then vertex v must have at least two neighbors assigned 2 under f or one neighbor w with \(f(w)=3\) f ( w ) = 3 , and if \(f(v)=1\) f ( v ) = 1 , then vertex v must have at least one neighbor w with \(f(w)\ge 2\) f ( w ) 2 . The weight of a DRDF is the sum of its function values over all vertices, and the double Roman domination number \(\gamma _{dR}(G)\) γ dR ( G ) is the minimum weight of a DRDF on G. Khoeilar et al. (Discrete Appl. Math. 270:159–167, 2019) proved that if G is a connected graph of order n with minimum degree two different from \(C_{5}\) C 5 and \(C_{7}\) C 7 , then \(\gamma _{dR}(G)\le \frac{11}{10}n.\) γ dR ( G ) 11 10 n . Moreover, they presented an infinite family of graphs \({\mathcal {G}}\) G attaining the upper bound, and conjectured that \({\mathcal {G}}\) G is the only family of extremal graphs reaching the bound. In this paper, we disprove this conjecture by characterizing all extremal graphs for this bound.