Celoštevilski graf

Celoštevilski graf (tudi integralni graf) je v teoriji grafov graf katerega spekter je v celoti sestavljen iz celih števil. Ali drugače – graf je celoštevilski, če in samo če so vse njegove lastne vrednosti karakterističnega polinoma cela števila.

Pojem celoštevilskega grafa sta uvedla leta 1974 Harary in Schwenk.

Zgledi

• polni graf K_n je celoštevilski za vse n. Na primer tetraedrski graf K₄.
• prazni graf ${\overline{K}}_n$ je celoštevilski za vse n.
• med kubičnimi simetričnimi grafi so graf napeljav, Petersenov graf, Desarguesov graf in Naurujski graf celoštevilski.
• Higman-Simsov graf, Hall-Jankov graf, Clebschev graf, Hoffman-Singletonov graf, Hoffmanov graf in Šrikhandov graf so celoštevilski.

• 
  Polni graf K₁ (prazni graf N₁, ${\bar{K}}_1$)
• 
  Polni graf K₄ (tetraedrski graf)
• 
  Graf napeljav (Thomsenov graf K_3,3)
• 
  Petersenov graf
• 
  Hoffmanov graf
• 
  Šrikhandov graf
• 
  Clebschev graf
• 
  Desarguesov graf
• 
  Naurujski graf
• 
  Hoffman-Singletonov graf
• 
  Higman-Simsov graf
• 
  Hall-Jankov graf

Viri

• Predloga:Citat

Zunanje povezave

• Predloga:MathWorld