Several Roman domination graph invariants on Kneser graphs

Abstract

This paper considers the following three Roman domination graph invariants on Kneser graphs: Roman domination, total Roman domination, and signed Roman domination. For Kneser graph $K_{n,k}$, we present exact values for Roman domination number ${\gamma }_R(K_{n,k})$ and total Roman domination number ${\gamma }_{tR}(K_{n,k})$ proving that for $n⩾k(k+1)$, ${\gamma }_R(K_{n,k})={\gamma }_{tR}(K_{n,k})=2(k+1)$. For signed Roman domination number ${\gamma }_{sR}(K_{n,k})$, the new lower and upper bounds for $K_{n,2}$ are provided: we prove that for $n⩾12$, the lower bound is equal to 2, while the upper bound depends on the parity of $n$ and is equal to 3 if $n$ is odd, and equal to $5$ if $n$ is even. For graphs of smaller dimensions, exact values are found by applying exact methods from literature.

References in corpus (2)

• Solving the signed Roman domination and signed total Roman domination problems with exact and heuristic methods
• Signed Roman Domination Number and Join of Graphs