Sesión Matemática Discreta

Sobre grafos de distancia de Kneser

Agustina Victoria Ledezma

Instituto de Matemática Aplicada San Luis (UNSL-CONICET) y Departamento de Matemática, Universidad Nacional de San Luis, Argentina   -   Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.

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$.

Trabajo en conjunto con: Mario Valencia-Pabon (Université de Lorraine, LORIA, Nancy, France) y Adrián Pastine (Instituto de Matemática Aplicada San Luis (UNSL-CONICET) y Departamento de Matemática, Universidad Nacional de San Luis, San Luis, Argentina).

Referencias

[1] Brešar, B., Gastineau, N., Klavžar, S., & Togni, O. (2019). Exact distance graphs of product graphs. Graphs and Combinatorics, 35(6), 1555-1569.

[2] Chen, Y., & Wang, Y. (2008). On the diameter of generalized Kneser graphs. Discrete mathematics, 308(18), 4276-4279.

[3] Frankl, P., & Füredi, Z. (1986). Extremal problems concerning Kneser graphs. Journal of Combinatorial Theory, Series B, 40(3), 270-284.

[4] Lovász, L. (1978). Kneser's conjecture, chromatic number, and homotopy. Journal of Combinatorial Theory, Series A, 25(3), 319-324.

[5] Stahl, S. (1976). n-Tuple colorings and associated graphs. Journal of Combinatorial Theory, Series B, 20(2), 185-203.

[6] Valencia-Pabon, M., & Vera, J. C. (2005). On the diameter of Kneser graphs. Discrete mathematics, 305(1-3), 383-385.

Ver resumen en PDF