Цілий граф

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

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

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