| Naslov: | $k$-domination invariants on Kneser graphs |
|---|
| Avtorji: | ID Brešar, Boštjan (Avtor)
ID Dravec, Tanja (Avtor)
ID Cornet, María Gracia (Avtor)
ID Henning, Michael A. (Avtor) |
|---|
| Datoteke: |  PDF - Predstavitvena datoteka, prenos (377,04 KB)
MD5: 66EC8CE06F64C6DE4D26867E1D16C882
 URL - Izvorni URL, za dostop obiščite https://amc-journal.eu/index.php/amc/article/view/3294
|
|---|
| Jezik: | Angleški jezik |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: |  IMFM - Inštitut za matematiko, fiziko in mehaniko
|
|---|
| Povzetek: | 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.
|
|---|
| Ključne besede: | Kneser graphs, k-domination, k-tuple total domination, 2-packing |
|---|
| Status publikacije: | Objavljeno |
|---|
| Verzija publikacije: | Objavljena publikacija |
|---|
| Datum objave: | 01.01.2025 |
|---|
| Leto izida: | 2025 |
|---|
| Št. strani: | 16 str. |
|---|
| Številčenje: | Vol. 25, no. 4, [article no.] P4.02 |
|---|
| PID: | 20.500.12556/DiRROS-23096  |
|---|
| UDK: | 519.17 |
|---|
| ISSN pri članku: | 1855-3966 |
|---|
| DOI: | 10.26493/1855-3974.3294.7fd |
|---|
| COBISS.SI-ID: | 243733251 |
|---|
| Opomba: |
|
|---|
| Datum objave v DiRROS: | 24.07.2025 |
|---|
| Število ogledov: | 419 |
|---|
| Število prenosov: | 237 |
|---|
| Metapodatki: |    |
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
