Целый граф

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

Примеры:

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

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