| Title: | $k$-domination invariants on Kneser graphs |
|---|
| Authors: | ID Brešar, Boštjan (Author)
ID Dravec, Tanja (Author)
ID Cornet, María Gracia (Author)
ID Henning, Michael A. (Author) |
|---|
| Files: |  PDF - Presentation file, download (377,04 KB)
MD5: 66EC8CE06F64C6DE4D26867E1D16C882
 URL - Source URL, visit https://amc-journal.eu/index.php/amc/article/view/3294
|
|---|
| Language: | English |
|---|
| Typology: | 1.01 - Original Scientific Article |
|---|
| Organization: |  IMFM - Institute of Mathematics, Physics, and Mechanics
|
|---|
| Abstract: | In this follow-up to work of M.G. Cornet and P. Torres from 2023, where the $k$-tuple domination number and the $2$-packing number in Kneser graphs $K(n,r)$ were studied, we are concerned with two variations, the $k$-domination number, $\gamma_k(K(n,r))$, and the $k$-tuple total domination number, $\gamma_{t\times k}(K(n,r))$, of $K(n,r)$. For both invariants we prove monotonicity results by showing that $\gamma_k(K(n,r))\ge \gamma_k(K(n+1,r))$ holds for any $n\ge 2(k+r)$, and $\gamma_{t\times k}(K(n,r))\ge \gamma_{t\times k}(K(n+1,r))$ holds for any $n\ge 2r+1$. We prove that $\gamma_k(K(n,r))= \gamma_{t\times k}(K(n,r))= k+r$ when $n\geq r(k+r)$, and that in this case every $\gamma_k$-set and $\gamma_{t\times k}$-set is a clique, while $\gamma_k(r(k+r)-1,r)=\gamma_{t\times k}(r(k+r)-1,r)=k+r+1$, for any $k\ge 2$. Concerning the $2$-packing number, $\rho_2(K(n,r))$, of $K(n,r)$, we prove the exact values of $\rho_2(K(3r-3,r))$ when $r\ge 10$, and give sufficient conditions for $\rho_2(K(n,r))$ to be equal to some small values by imposing bounds on $r$ with respect to $n$. We also prove a version of monotonicity for the $2$-packing number of Kneser graphs.
|
|---|
| Keywords: | Kneser graphs, k-domination, k-tuple total domination, 2-packing |
|---|
| Publication status: | Published |
|---|
| Publication version: | Version of Record |
|---|
| Publication date: | 01.01.2025 |
|---|
| Year of publishing: | 2025 |
|---|
| Number of pages: | 16 str. |
|---|
| Numbering: | Vol. 25, no. 4, [article no.] P4.02 |
|---|
| PID: | 20.500.12556/DiRROS-23096  |
|---|
| UDC: | 519.17 |
|---|
| ISSN on article: | 1855-3966 |
|---|
| DOI: | 10.26493/1855-3974.3294.7fd |
|---|
| COBISS.SI-ID: | 243733251 |
|---|
| Note: |
|
|---|
| Publication date in DiRROS: | 24.07.2025 |
|---|
| Views: | 423 |
|---|
| Downloads: | 239 |
|---|
| Metadata: |    |
|---|
|
:
|
Copy citation |
|---|
| | | | Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
