Integrální graf - Integral graph

V matematický pole teorie grafů, an integrální graf je graf, jehož matice sousedství je spektrum skládá se výhradně z celých čísel. Jinými slovy, graf je integrálním grafem, pokud všechny kořeny z charakteristický polynom jeho matice sousedství jsou celá čísla.^[1]

Pojem zavedla v roce 1974 Harary a Schwenk.^[2]

Příklady

• The kompletní graf K._n je integrální pro všechny n.
• The bez okrajů graf ${ displaystyle { bar {K}} _ {n}}$ je integrální pro všechny n.
• Mezi kubickými symetrickými grafy obslužný graf, Petersenův graf, Nauru graf a Desargues graf jsou integrální.
• The Graf Higman – Sims, Hall – Jankov graf, Clebschův graf, Hoffman – Singletonův graf, Shrikhandův graf a Hoffmanův graf jsou integrální.
• A běžný graf je periodicky právě když se jedná o integrální graf.
• A běžný graf to připouští dokonalý přenos stavu je integrální graf.
• The Sudoku grafy, grafy, jejichž vrcholy představují buňky desky Sudoku a jejichž hrany představují buňky, které by neměly být stejné, jsou integrální.^[3]

Reference