Цілий граф

В області математичної теорії графів, цілий або інтегральний граф (англ. Integral graph) — це граф, спектр якого повністю складається з цілих чисел.

Іншими словами, граф є інтегральним графом, якщо всі власні значення його характеристичного полінома є цілими числами. Поняття ввели в 1974 році Харарі і Швенк.

Приклади

• Повний граф K_n є цілим для всіх n.
• ^[en] ${\displaystyle {\overline {K_{n}}}}$ є цілим для всіх n.
• Серед симетричних кубічних графів ресурсний граф, граф Петерсена, граф Науру і граф Дезарга є цілими.
• Граф Гіґмана — Сімса, граф Голла — Янко, граф Клебша, граф Гофмана — Синглтона, граф Шрікханде, граф Берлекемпа — ван Лінта — Зейделя і граф Гофмана є цілими.

Посилання

1. Weisstein, Eric W. «Integral Graph». 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.