Целый граф

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

Примеры:

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

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