En matemáticas , en teoría de grafos , la matriz de adyacencia de Seidel de un grafo simple no dirigido G es una matriz simétrica con una fila y columna para cada vértice, que tiene 0 en la diagonal, -1 para posiciones cuyas filas y columnas corresponden a vértices adyacentes, y +1 para posiciones correspondientes a vértices no adyacentes. También se denomina matriz de Seidel o, su nombre original, matriz de adyacencia (-1,1,0) . Se puede interpretar como el resultado de restar la matriz de adyacencia de G de la matriz de adyacencia del complemento de G .
El conjunto múltiple de valores propios de esta matriz se denomina espectro de Seidel .
La matriz de Seidel fue introducida por JH van Lint y JJ Seidel en 1966 y ampliamente explotada por Seidel y sus coautores.
La matriz de Seidel de G es también la matriz de adyacencia de un gráfico completo con signo K G en el que los bordes de G son negativos y los bordes que no están en G son positivos. También es la matriz de adyacencia de la dos-gráfico asociado con G y K G .
Las propiedades de valor propio de la matriz de Seidel son valiosas en el estudio de gráficos fuertemente regulares .
Referencias
- van Lint, JH y Seidel, JJ (1966), Conjuntos de puntos equiláteros en geometría elíptica. Indagationes Mathematicae , vol. 28 (= Proc. Kon. Ned. Aka. Wet. Ser. A , vol. 69), págs. 335–348.
- Seidel, JJ (1976), A survey of two-graphs. En: Colloquio Internazionale sulle Teorie Combinatorie (Actas, Roma, 1973), vol. I, págs. 481–511. Atti dei Convegni Lincei, No. 17. Accademia Nazionale dei Lincei, Roma.
- Seidel, JJ (1991), ed. DG Corneil y R. Mathon, Geometría y combinatoria: obras seleccionadas de JJ Seidel . Boston: Prensa académica. Muchos de los artículos involucran la matriz de Seidel.
- Seidel, JJ (1968), Gráficos fuertemente regulares con matriz de adyacencia (-1,1,0) que tiene valor propio 3. Álgebra lineal y sus aplicaciones 1, 281-298.