$k$-Domination invariants on Kneser graphs
| Autor: | Brešar, Boštjan, Cornet, María Gracia, Dravec, Tanja, Henning, Michael A. |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | In this follow-up to [M.G.~Cornet, P.~Torres, arXiv:2308.15603], 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. Comment: 15 pages, 3 tables |
| Databáze: | arXiv |
| Externí odkaz: |
|