El parámetro de k-upla dominación en grafos de Kneser

CORNET, MARÍA GRACIA; TORRES, PABLO

Bahía Blanca

Congreso; XVII Congreso Dr. A. Monteiro; 2023

Universidad Nacional del Sur

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 ...(referencias).Dados dos naturales $n$, $r$ con $n>2r$, el emph{grafo de Kneser} $Kneser{n}{r}$ tiene conjunto de vértices $V={vsubseteq [n]:|v|=r}$ y conjunto de aristas $E={uv:ucap 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 número natural $kleq delta(G)+1$, un conjunto $k$ -upla dominante $D$ es un subconjunto de $V$ tal que $|N[u]cap D|geq k$ para cada $uin V$. El número de $k$-upla dominación $dom{G}{imes k}$ 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 $dom{Kneser{n}{r}}{imes k}$ 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 $dom{Kneser{n}{2}}{imes k}$.