Tatjana Zec ; Milana Grbić - Several Roman domination graph invariants on Kneser graphs

dmtcs:10506 - Discrete Mathematics & Theoretical Computer Science, May 26, 2023, vol. 25:1 - https://doi.org/10.46298/dmtcs.10506
Several Roman domination graph invariants on Kneser graphsArticle

Authors: Tatjana Zec ; Milana Grbić

    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\geqslant 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\geqslant 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.

    Volume: vol. 25:1
    Section: Graph Theory
    Published on: May 26, 2023
    Accepted on: April 25, 2023
    Submitted on: December 19, 2022
    Keywords: Mathematics - Combinatorics

    1 Document citing this article

    Consultation statistics

    This page has been seen 542 times.
    This article's PDF has been downloaded 436 times.