Several Roman domination graph invariants on Kneser graphs

DOI10.46298/DMTCS.10506MaRDI QIDQ6131794zbMATH OpenFDO

Authors Milana Grbić

Publication date 18 April 2024

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

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

zbMATH Keywords

Kneser graphsRoman dominationsigned Roman dominationtotal Roman domination

Mathematics Subject Classification ID

Combinatorics (05-XX)

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.

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

Cited in

(3)

• Total Roman domination on Kneser graphs
• On double Roman domination problem for several graph classes
• k-tuple domination in Kneser graphs

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)