Întregul grafic

Un grafic întreg ( integer graph ) este un grafic al cărui spectru de matrice de adiacență ( graph invariant ) este format în întregime din numere întregi. Cu alte cuvinte, un graf este un graf întreg, cu condiția ca toate rădăcinile polinomului caracteristic al matricei sale de adiacență să fie numere întregi [1] . Conceptul a fost introdus în 1974 de către Harari și Schwenk [2] .

Exemple:

graficul complet este întreg pentru toate ; $K_n$ $n$
un grafic fără muchii este un număr întreg pentru toate ; ${\bar {K}}_{n}$ $n$
printre graficele simetrice cubice , graficul comunal , graficul Petersen , graficul Nauru și graficul Desargues sunt numere întregi ;
numărul Higman-Sims , numărul Hall-Janko , numărul Clebsch , numărul Hoffman-Singleton , numărul Shrikhande și numărul Hoffman sunt de asemenea numere întregi ;
Graficele Sudoku ale căror vârfuri reprezintă celulele câmpului Sudoku și ale căror margini reprezintă celule care nu trebuie să fie egale sunt grafice întregi [3] .

Un grafic obișnuit este periodic dacă și numai dacă este întreg. Un grafic de mers obișnuit care îndeplinește condițiile pentru un transfer ideal al unei stări cuantice este un întreg grafic.

Note

^ Weisstein , Eric W. Integral Graph pe site- ul Wolfram MathWorld .
↑ Harary F., Schwenk AJ Care grafice au spectre integrale? // Grafice și combinatorie / R. Bari și F. Harary. - Berlin: Springer-Verlag, 1974. - S. 45-51.
↑ Torsten Sander. Graficele sudoku sunt integrale // Electronic Journal of Combinatorics. - 2009. - T. 16 , nr. 1 . - S. Nota 25, 7 .