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!
|
| _version_ | 1850056443657453568 |
|---|---|
| author | Tatjana Zec Milana Grbić |
| author_facet | Tatjana Zec Milana Grbić |
| author_sort | Tatjana Zec |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-1bb9ddb33c7345848fb35569be04b383 |
| institution | DOAJ |
| issn | 1365-8050 |
| language | English |
| publishDate | 2023-05-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj-art-1bb9ddb33c7345848fb35569be04b3832025-08-20T02:51:42ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502023-05-01vol. 25:1Graph Theory10.46298/dmtcs.1050610506Several Roman domination graph invariants on Kneser graphsTatjana ZecMilana 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.http://dmtcs.episciences.org/10506/pdfmathematics - combinatorics |
| spellingShingle | Tatjana Zec Milana Grbić Several Roman domination graph invariants on Kneser graphs Discrete Mathematics & Theoretical Computer Science mathematics - combinatorics |
| title | Several Roman domination graph invariants on Kneser graphs |
| title_full | Several Roman domination graph invariants on Kneser graphs |
| title_fullStr | Several Roman domination graph invariants on Kneser graphs |
| title_full_unstemmed | Several Roman domination graph invariants on Kneser graphs |
| title_short | Several Roman domination graph invariants on Kneser graphs |
| title_sort | several roman domination graph invariants on kneser graphs |
| topic | mathematics - combinatorics |
| url | http://dmtcs.episciences.org/10506/pdf |
| work_keys_str_mv | AT tatjanazec severalromandominationgraphinvariantsonknesergraphs AT milanagrbic severalromandominationgraphinvariantsonknesergraphs |