Celý graf

Celočíselný graf  ( celočíselný graf ) je graf, jehož spektrum matice sousednosti ( graf invariant ) se skládá výhradně z celých čísel. Jinými slovy, graf je celočíselný graf za předpokladu, že všechny kořeny charakteristického polynomu jeho matice sousedství jsou celá čísla [1] . Tento koncept představili v roce 1974 Harari a Schwenk [2] .

Příklady:

• úplný graf je celé číslo pro všechny ;
• graf bez hran je celé číslo pro všechny ;
• mezi kubickými symetrickými grafy jsou komunální graf , Petersenův graf , Nauruův graf a Desarguesův graf celá čísla ;
• hrabě Higman-Sims , hrabě Hall-Janko , hrabě Clebsch , hrabě Hoffman-Singleton , hrabě Shrikhande a hrabě Hoffman jsou také celá čísla ;
• Sudoku grafy , jejichž vrcholy představují buňky pole Sudoku a jejichž hrany představují buňky, které se nemusí rovnat, jsou celočíselné grafy [3] .

Regulární graf je periodický právě tehdy, když je celočíselný. Běžný procházkový graf , který splňuje podmínky pro ideální přenos kvantového stavu , je celý graf.

Poznámky

1. ↑ Weisstein, Eric W. Integral Graph  na webu Wolfram MathWorld .
2. ↑ Harary F., Schwenk AJ Které grafy mají integrální spektra? // Grafy a kombinatorika / R. Bari a F. Harary. - Berlín: Springer-Verlag, 1974. - S. 45-51.
3. ↑ Torsten Sander. Grafy sudoku jsou integrální  // Electronic Journal of Combinatorics. - 2009. - T. 16 , no. 1 . - S. Poznámka 25, 7 .