Интегральный график

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

Это понятие было введено в 1974 году Фрэнком Харари и Алленом Швенком.

Примеры

• Полный граф Kn _n является целым для всех .
• Единственными графами циклов , которые являются целыми, являются $C_{3}$, $C_{4}$, и $C_{6}$.
• Если граф является целым, то таким же является и его граф дополнений ; например, дополнения полных графов, графы без ребер , являются целыми. Если два графа целочисленны, то целочисленны и их декартово произведение и сильное произведение ; например, декартовы произведения двух полных графов, ладейных графов , являются целыми. Аналогично, графы гиперкуба как декартово произведение любого количества полных графов $K_{2}$, являются целыми.
• Линейный график интегрального графа снова является целым. Например, как линейный график $K_{4}$, октаэдрический граф целочислен и как дополнение к линейному графу $K_{5}$, граф Петерсена является целым.
• Среди кубических симметричных графов целочисленными являются граф полезности , граф Петерсена , граф Науру и граф Дезарга .
• Граф Хигмана -Симса , граф Холла-Янко , граф Клебша , граф Хоффмана-Синглтона , граф Шрикханде и граф Хоффмана являются целыми.
• Регулярный граф является периодическим тогда и только тогда, когда он является целым графом.
• , Регулярный граф допускающий идеальную передачу состояний, является интегральным графом.
• Графы судоку — графы, вершины которых представляют ячейки доски судоку, а ребра — ячейки, которые не должны быть равными, являются целыми.