Roman domination in graphs with minimum degree at least two and some forbidden cycles

Abstract

Let $G=(V,E)$ be a graph of order $n$ and let ${\gamma }_R(G)$ and $\partial (G)$ denote the Roman domination number and the differential of $G,$ respectively. In this paper we prove that for any integer $k\ge 0$, if $G$ is a graph of order $n\ge 6k+9$, minimum degree $\delta \ge 2,$ which does not contain any induced $\{C_5,C_8,\dots ,C_{3k+2}\}$% -cycles, then ${\gamma }_R(G)\le \frac{(4k+8)n}{6k+11}$. This bound is an improvement of the bounds given in [E.W. Chambers, B. Kinnersley, N. Prince, and D.B. West, Extremal problems for Roman domination, SIAM J. Discrete Math. 23 (2009) 1575--1586] when $k=0,$ {and [S. Bermudo, On the differential and Roman domination number of a graph with minimum degree two, Discrete Appl. Math. 232 (2017), 64--72] when }$k=1.$ Moreover, using the Gallai-type result involving the Roman domination number and the differential of graphs established by Bermudo et al. stating that ${\gamma }_R(G)+\partial (G)=n$, we have $\partial (G)\ge \frac{(2k+3)n}{6k+11},$ thereby settling the conjecture of Bermudo posed in the second paper.