UMA 2022
La dominación en grafos es uno de los tópicos más fértiles en el área. Esta dio lugar a muchas variantes que han sido estudiadas en diversas clases de grafos, entre ellas en Grafos de Kneser, como por ejemplo en [1], [2], [3], [4].
Dados dos naturales $n$, $r$ con $n > 2r$, el grafo de Kneser $Kn(n,r)$ tiene conjunto de vértices $V=\{v\subseteq [n]:|v|=r\}$ y conjunto de aristas $E=\{uv:u\cap v=\emptyset\}$.
Entre las variantes más estudiadas de dominación, se encuentra la $k$-upla dominación. Dados un grafo $G=(V,E)$ y un número natural $k\leq \delta(G)+1$, un conjunto $k$ -upla dominante $D$ es un subconjunto de $V$ tal que $|N[u]\cap D|\geq k$ para cada $u\in V$. El número de $k$-upla dominación $\gamma_{\times k}(G)$ es el mínimo cardinal de un conjunto $k$-upla dominante de $G$.
En este trabajo estudiamos la $k$-upla dominación en grafos de Kneser. Obtenemos cotas generales para $\gamma_{\times k}(Kn(n,r))$ y demostramos que en algunos casos son ajustadas. Analizamos los conjuntos $k$-upla dominantes para el caso $r=2$ lo que nos permite obtener nuevas cotas y valores exactos para $\gamma_{\times k}(Kn(n,2))$.
Trabajo en conjunto con: Pablo Torres (UNR - CONICET, Argentina).
Referencias
[1] Behtoei, A., & Jalilolghadr, P. (2020). Total dominator chromatic number of Kneser graphs. arXiv preprint arXiv:2001.00221.
[2] Brešar, B., Kos, T., & Torres, P. D. (2019). Grundy domination and zero forcing in Kneser graphs. ARS MATHEMATICA CONTEMPORANEA, 17(2), 419-430.
[3] Gorodezky, I. (2007). Dominating sets in Kneser graphs (Master’s thesis, University of Waterloo)
[4] Östergård, P. R., Shao, Z., & Xu, X. (2014). Bounds on the domination number of Kneser graphs. ARS MATHEMATICA CONTEMPORANEA, 9(2), 187-195.