Sesión Matemática DiscretaSobre una generalización de grafos distancia regular, autovectores constantes y autovalores lineales
Ezequiel Dratman
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$, se define el grafo $G_i$ de distancia-$i$ al grafo cuyo conjunto de vértices es $V(G)$, y dos vértices $u$ y $v$ son adyacentes si y solo si $d(u, v)= i$ en $G$. Llamaremos matriz de distancia-$i$ de $G$ a la matriz de adyacencia $A_i$ de $G_i$. Un grafo $G$ se denomina distancia regular si para todo par de vértices $u$ y $v$ con $d(u, v)=k$, la cantidad de vértices $z$ con $d(u, z)=i$ y $d(z, v)=j$ es una constante que sólo depende de $i$, $j$ y $k$ [1]. Estos grafos son un concepto clave en Combinatoria Algebraica [2] y han dado lugar a varias generalizaciones, como los esquemas de asociación [3]. En particular, las matrices de distancia-$i$ de un grafo distancia regular conmutan, de donde se puede deducir que todas estas matrices son mutuamente diagonalizables, es decir, comparten todos los autovectores [4].
En esta comunicación, presentaremos una caracterización de la familia de grafos cuyas matrices de distancia-$i$ son mutuamente diagonalizables, y mostraremos que la familia de grafos distancia regular esta incluida propiamente en la anterior. Además, para estas familias, probaremos propiedades de los autovalores y autovectores de las matrices clásicas asociadas a un grafo, es decir, matriz de adyacencia, distancia, laplaciana, etc.
Trabajo en conjunto con: Cristian M. Conde (Universidad Nacional de General Sarmiento), Verónica Moyano (Universidad Nacional de General Sarmiento) y Adrián Pastine (Universidad Nacional de San Luis).
Referencias
[1] A.E. Brouwer, A.M. Cohen, A. Neumaier, Distance-Regular Graphs, Springer-Verlag, Berlin/New York, 1989.
[2] C.D. Godsil, Algebraic Combinatorics, Chapman and Hall, New York, 1993.
[3] W.J. Martin, H. Tanaka, Commutative association schemes, European J. Combin. 30 (2009) 1497–1525.
[4] G. Strang, Linear Algebra and its Application, Cengage Learning, 2006.