Sesión Matemática DiscretaRango de matriz de distancia en grafos
Verónica Moyano
Universidad Nacional de General Sarmiento, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Dado un grafo conexo $G$ con vértices $V=\{v_1,...,v_n\}$, se define la entrada $(i,j)$ de la matriz de distancia $D(G)$ como la distancia entre los vértices $v_i$ y $v_j$ en $G$. Usando resultados de la teoría de Ramsey probamos que para cada entero $k\geq 2$, existe una cantidad finita de grafos cuya matriz de distancia tienen rango $k$. Además describimos los grafos cuyas matrices de distancia tienen rango 2 y 3.
Se definen los grafos trivially perfect como los grafos en que, para todo subgrafo inducido $H$ el tamaño del conjunto independiente máximo en $H$ coincide con la cantidad de cliques maximales en $H$. Veremos que en esta clase de grafos se cumple que para cada $\eta\geq 1$ existe un grafo trivially perfect cuya matriz de distancia tiene nulidad $\eta$. Además, para los grafos threshold, una subfamilia de los trivially perfect, veremos que la nulidad está acotada por 1.
Trabajo en conjunto con: Ezequiel Dratman (Universidad Nacional de General Sarmiento), Luciano Grippo (Universidad Nacional de General Sarmiento), Adrián Pastine (Universidad Nacional de San Luis).