Целый граф

Целый граф (целочисленный граф) — граф, спектр матрицы смежности (инвариант графа) которого состоит полностью из целых чисел. Другими словами, граф является целым графом, при условии, что все корни характеристического многочлена его матрицы смежности являются целыми числами. Понятие ввели в 1974 году Харари и Швенк.

Примеры:

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

Регулярный граф является периодическим тогда и только тогда, когда он целый. Граф регулярных блужданий, удовлетворяющий условиям идеальной передачи квантового состояния, является целым графом.