Egész grafikon

Az egész gráf  ( integer graph ) olyan gráf, amelynek szomszédsági mátrix spektruma ( gráfinvariáns ) teljes egészében egész számokból áll. Más szóval a gráf egész gráf, feltéve, hogy szomszédsági mátrixának karakterisztikus polinomjának minden gyöke egész szám [1] . A koncepciót 1974 -ben vezette be Harari és Schwenk [2] .

Példák:

• a teljes gráf mindenre egész ;
• élek nélküli gráf egész szám mindenre ;
• a köbös szimmetrikus gráfok közül a kommunális gráf , a Petersen -gráf , a Nauru -gráf és a Desargues-gráf egész számok ;
• a Higman-Sims gróf , a Hall-Janko gróf , a Clebsch gróf , a Hoffman-Singleton gróf , a Shrikhande gróf és a Hoffman gróf is egész számok ;
• Azok a Sudoku gráfok , amelyek csúcsai a Sudoku mező celláit képviselik, élei pedig azokat a cellákat, amelyeknek nem kell egyenlőnek lenniük, egész gráfok [3] .

Egy szabályos gráf akkor és csak akkor periodikus , ha egész szám. Egy szabályos sétagráf , amely kielégíti a kvantumállapot ideális átvitelének feltételeit, egy teljes gráf.

Jegyzetek

1. ↑ Weisstein, Eric W. Integral Graph  a Wolfram MathWorld webhelyen .
2. ↑ Harary F., Schwenk AJ Mely gráfoknak van integrál spektruma? // Grafikonok és kombinatorika / R. Bari és F. Harary. - Berlin: Springer-Verlag, 1974. - S. 45-51.
3. ↑ Torsten Sander. A Sudoku grafikonok szerves részét képezik  // Electronic Journal of Combinatorics. - 2009. - T. 16 , sz. 1 . - S. 25., 7. jegyzet .