Sobre grafos de distancia de Kneser

ADRIÁN PASTINE; MARIO VALENCIA-PABON; AGUSTINA VICTORIA LEDEZMA

Salta

Conferencia; Reunión Anual de la Unión Matemática Argentina 2023; 2023

Dados $k,r$ enteros positivos, definimos$[2k+r] = {1,2,ldots,2k+r}$, y $[2k+r]^k$ el conjunto de $k$-subconjuntos de $[2k+r]$. El grafo de Kneser $K(2k+r,k)$ es el grafo cuyo conjunto de vértices es$[2k+r]^k$ y donde dos $k$-subconjuntos $A,B in [2k+r]^k$ son adyacentes si y solo si $A cap B = emptyset$.Sean $G = (V,E)$ un grafo y $D$ su diámetro. Para un entero fijo $d$, con $1 leq d leq D$, el grafo de $d$-distancia exacta de $G$, denotado por $G_{=d}$, es el grafo que posee el mismo conjunto de vértices $V$ de $G$, y donde dos vértices $a,b in G_{=d}$ son adyacentes si y solo si su distancia en $G$ es igual a $d$. Este tipo de grafos ha sido estudiado mayormente por sus aplicaciones a problemas de coloreo.En este trabajo caracterizamos la relación de adyacencia de los vértices en el grafo de $d$-distancia exacta de Kneser $K_{=d}(2k+r,k)$ y calculamos la función distancia entre cualquier par de vértices no adyacentes, en términos de la cardinalidad de su intersección como $k$-conjuntos de $[2k+r]^k$.