En la matemática campo de la teoría de grafos , una gráfica integral es un gráfico cuya matriz de adyacencia 's espectro consiste enteramente de números enteros. En otras palabras, un gráfico es un gráfico integral si todas las raíces del polinomio característico de su matriz de adyacencia son números enteros. [1]
Ejemplos de
- El gráfico completo K n es integral para todo n .
- El gráfico sin bordes es integral para todo n .
- Entre los gráficos simétricos cúbicos, el gráfico de utilidad , el gráfico de Petersen , el gráfico de Nauru y el gráfico de Desargues son integrales.
- El gráfico Higman-Sims , el gráfico de Hall-Janko , el gráfico Clebsch , el gráfico de Hoffman-Singleton , el gráfico Shrikhande y el gráfico Hoffman son integral.
- Una gráfica regular es periódica si y solo si es una gráfica integral.
- Un gráfico de caminata regular que admite una transferencia de estado perfecta es un gráfico integral.
- Las gráficas de Sudoku , gráficas cuyos vértices representan celdas de un tablero de Sudoku y cuyos bordes representan celdas que no deberían ser iguales, son integrales. [3]
Referencias
- ^ Weisstein, Eric W. "Gráfico integral" . MathWorld .
- ^ Harary, F. y Schwenk, AJ "¿Qué gráficos tienen espectros integrales?" En Gráficos y Combinatoria (Ed. R. Bari y F. Harary). Berlín: Springer-Verlag, págs. 45–51, 1974.
- ^ Sander, Torsten (2009), "Los gráficos de Sudoku son integrales" , Electronic Journal of Combinatorics , 16 (1): Nota 25, 7, MR 2529816