Цілий граф
В області математичної теорії графів, цілий або інтегральний граф (англ. Integral graph) — це граф, спектр якого повністю складається з цілих чисел.
Іншими словами, граф є інтегральним графом, якщо всі власні значення його характеристичного полінома є цілими числами.[1] Поняття ввели в 1974 році Харарі і Швенк.[2]
Приклади
- Повний граф Kn є цілим для всіх n.
- Безреберний граф є цілим для всіх n.
- Серед симетричних кубічних графів ресурсний граф, граф Петерсена, граф Науру і граф Дезарга є цілими.
- Граф Хігмана — Сімса, граф Голла — Янко, граф Клебша, граф Гофмана — Синглтона, граф Шрікханде і граф Хоффмана є цілими.
Посилання
- Weisstein, Eric W. «Integral Graph». MathWorld.
- 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.