Roman domination problem on Johnson graphs

Abstract

In this paper Roman domination problem for Johnson graphs $J_{n,2}$ and $J_{n,3}$ is considered. For $J_{n,2}$, $n \geqslant 4$ it is proved that $\gamma_R(J_{n,2}) = n-1$. For $J_{n,3}, n\geqslant 6$ new lower and upper bounds, which quadratically depend on the dimension $n$, are given.