Gráfica integral

En el campo matemático de la teoría de grafos , un grafo integral es un grafo cuyo espectro de la matriz de adyacencia está compuesto enteramente de números enteros. En otras palabras, un grafo es un grafo integral si todas las raíces del polinomio característico de su matriz de adyacencia son números enteros. ^[1]

El concepto fue introducido en 1974 por Frank Harary y Allen Schwenk. ^[2]

Ejemplos

• El gráfico completo K _n es integral para todo n . ^[2]
• Los únicos gráficos de ciclo que son integrales son , , y . ^[2] ${\displaystyle C_{3}}$ ${\displaystyle C_{4}}$ ${\displaystyle C_{6}}$
• Si un grafo es integral, entonces también lo es su grafo complementario ; por ejemplo, los complementos de grafos completos, grafos sin aristas , son integrales. Si dos grafos son integrales, entonces también lo son su producto cartesiano y su producto fuerte ; ^[2] por ejemplo, los productos cartesianos de dos grafos completos, los grafos de la torre , son integrales. ^[3] De manera similar, los grafos hipercubicos , como productos cartesianos de cualquier número de grafos completos , son integrales. ^[2] ${\displaystyle K_{2}}$
• El gráfico lineal de un gráfico integral es a su vez integral. Por ejemplo, como gráfico lineal de , el gráfico octaédrico es integral, y como complemento del gráfico lineal de , el gráfico de Petersen es integral. ^[2] ${\displaystyle K_{4}}$ ${\displaystyle K_{5}}$
• Entre los grafos simétricos cúbicos el grafo de utilidad , el grafo de Petersen , el grafo de Nauru y el grafo de Desargues son integrales.
• El gráfico de Higman-Sims , el gráfico de Hall-Janko , el gráfico de Clebsch , el gráfico de Hoffman-Singleton , el gráfico de Shrikhande y el gráfico de Hoffman son integrales.
• Un gráfico regular es periódico si y sólo si es un gráfico integral.
• Un gráfico regular que admite una transferencia de estado perfecta es un gráfico integral.
• Los gráficos de Sudoku , gráficos cuyos vértices representan celdas de un tablero de Sudoku y cuyos bordes representan celdas que no deben ser iguales, son integrales. ^[4]

Referencias

1. Weisstein, Eric W. , "Gráfico integral", MathWorld
2. Harary, Frank ; Schwenk, Allen J. (1974), "¿Qué grafos tienen espectros integrales?", en Bari, Ruth A. ; Harary, Frank (eds.), Gráficos y combinatoria: actas de la Conferencia Capital sobre teoría de grafos y combinatoria en la Universidad George Washington, Washington, DC, 18-22 de junio de 1973 , Lecture Notes in Mathematics, vol. 406, Springer, pp. 45-51, doi :10.1007/BFb0066434, MR  0387124
3. Doob, Michael (1970), "Sobre la caracterización de ciertos gráficos con cuatro valores propios por sus espectros", Álgebra lineal y sus aplicaciones , 3 : 461–482, doi : 10.1016/0024-3795(70)90037-6 , MR  0285432
4. Sander, Torsten (2009), "Los gráficos de sudoku son integrales", Electronic Journal of Combinatorics , 16 (1): Nota 25, 7, MR  2529816