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 por 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 ]}

La noción fue introducida en 1974 por Frank Harary y Allen Schwenk. ^{[ 2 ]}

• El grafo completo K _n es integral para todo n . ^{[ 2 ]}
• Los únicos gráficos cíclicos que son enteros son${\displaystyle C_{3}}$,${\displaystyle C_{4}}$, y${\displaystyle C_{6}}$. ^{[ 2 ]}
• Si un grafo es integral, entonces también lo es su grafo complemento ; por ejemplo, los complementos de grafos completos, los 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 hipercubo , como productos cartesianos de cualquier número de grafos completos${\displaystyle K_{2}}$, son integrales. ^{[ 2 ]}
• La gráfica de línea de una gráfica integral regular es nuevamente integral. Por ejemplo, como la gráfica de línea de${\displaystyle K_{4}}$, el gráfico octaédrico es integral y como complemento del gráfico de línea de${\displaystyle K_{5}}$, el gráfico de Petersen es integral. ^{[ 2 ]}
• Entre los grafos cúbicos simétricos , el grafo de utilidad , el grafo de Petersen , el grafo de Nauru y el grafo de Desargues son integrales.
• El grafo de Higman-Sims , el grafo de Hall-Janko , el grafo de Clebsch , el grafo de Hoffman-Singleton , el grafo de Shrikhande y el grafo de Hoffman son integrales.
• Una gráfica regular es periódica si y solo si es una gráfica integral.
• Un grafo regular por caminos que admite una transferencia de estado perfecta es un grafo integral.
• Los grafos de Sudoku , grafos cuyos vértices representan celdas de un tablero de Sudoku y cuyas aristas representan celdas que no deben ser iguales, son enteros. ^{[ 4 ]}