Several Roman domination graph invariants on Kneser graphs

DOI10.46298/DMTCS.10506arXiv2204.05664MaRDI QIDQ6131794FDOQ6131794

Authors: Milana Grbić 

Publication date: 18 April 2024

Published in: Discrete Mathematics & Theoretical Computer Science (Search for Journal in Brave)

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 $gamm{a}_R(K_{n,k})$ and total Roman domination number $gamm{a}_{tR}(K_{n,k})$ proving that for $ngeqslantk(k+1)$, $gamm{a}_R(K_{n,k})=gamm{a}_{tR}(K_{n,k})=2(k+1)$. For signed Roman domination number $gamm{a}_{sR}(K_{n,k})$, the new lower and upper bounds for $K_{n,2}$ are provided: we prove that for $ngeqslant12$, 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.

Full work available at URL: https://arxiv.org/abs/2204.05664

Recommendations

• On the signed Roman k-domination in graphs
• Bounds on the domination number of Kneser graphs
• The signed Roman \(k\)-domatic number of a graph
• Signed Roman \(k\)-domination in graphs

zbMATH Keywords

Roman dominationKneser graphstotal Roman dominationsigned Roman domination

Mathematics Subject Classification ID

Combinatorics (05-XX)

This page was built for publication: Several Roman domination graph invariants on Kneser graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6131794)