Several Roman domination graph invariants on Kneser graphs
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 num...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2023-05-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | http://dmtcs.episciences.org/10506/pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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. |
|---|---|
| ISSN: | 1365-8050 |