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

  • A Kn teljes gráf bármely n-re egész spektrumú.
  • A K ¯ n {\displaystyle {\bar {K}}_{n}} é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

  1. ↑ Weisstein, Eric W.: Integral Graph (angol nyelven). Wolfram MathWorld
  2. ↑ 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.