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

Примеры:

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

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

Примечания