Processing math: 25%

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 Kn,k, we present exact values for Roman domination number γR(Kn,k) and total Roman domination number γtR(Kn,k) proving that for n, \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

    Classifications

    1 Document citing this article

    Consultation statistics

    This page has been seen 698 times.
    This article's PDF has been downloaded 572 times.