Egész spektrumú gráf
A matematika, azon belül a gráfelmélet területén egy egész spektrumú gráf (integral graph) olyan gráf, melynek spektrumában csak egész számok szerepelnek. Más szavakkal, egy gráf akkor egész spektrumú, ha karakterisztikus polinomjának összes sajátértéke egész szám.[1]
Az egész spektrumú gráf fogalmát Harary és Schwenk vezették be 1974-ben.[2]
Példák
[szerkesztés]- A Kn teljes gráf bármely n-re egész spektrumú.
- A él nélküli gráf bármely n-re egész spektrumú.
- A 3-reguláris szimmetrikus gráfok közül a három ház–három kút-gráf, a Petersen-gráf, a Nauru-gráf és a Desargues-gráf egész spektrumú.
- 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 egész spektrumú.
Jegyzetek
[szerkesztés]- ↑ Weisstein, Eric W.: Integral Graph (angol nyelven). Wolfram MathWorld
- ↑ Harary, F. and Schwenk, A. J. "Which Graphs have Integral Spectra?" In Graphs and Combinatorics (Ed. R. Bari and F. Harary). Berlin: Springer-Verlag, pp. 45–51, 1974.