Целочисленный граф

Целочисленный граф — граф, спектр матрицы смежности которого полностью состоит из целых чисел. Другими словами, граф, все корни характеристического многочлена матрицы смежности которого являются целыми[1].

Понятие было введено в 1974 году Харари и Швенком[2].

Примеры:

• полный граф ${\displaystyle K_{n}}$ — целочисленный для всех ${\displaystyle n}$;
• безрёберный граф ${\displaystyle {\bar {K}}_{n}}$ является целочисленным для всех ${\displaystyle n}$;
• среди симметричных кубических графов граф Томсена, граф Петерсена, граф Науру и граф Дезарга являются целочисленными;
• графы Хигмана — Симса, Холла — Янко, Клебша, Хоффмана — Синглтона, Шриханде, Хоффмана являются целочисленными;
• регулярный граф является периодическим тогда и только тогда, когда он является целочисленным графом;
• граф регулярных блужданий, удовлетворяющий условиям идеальной передачи квантового состояния, является целочисленным графом;
• графы судоку являются целочисленными[3].