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

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

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

Примеры

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

Ссылки

1. Вайсштейн, Эрик В. , «Интегральный граф», MathWorld
2. Харари, Фрэнк ; Швенк, Аллен Дж. (1974), «Какие графы имеют интегральные спектры?», в Бари, Рут А .; Харари, Фрэнк (ред.), Графы и комбинаторика: Труды Капитальной конференции по теории графов и комбинаторике в Университете Джорджа Вашингтона, Вашингтон, округ Колумбия, 18–22 июня 1973 г. , Конспект лекций по математике, т. 406, Springer, стр. 45–51, doi :10.1007/BFb0066434, MR  0387124
3. Дуб, Майкл (1970), «О характеристике некоторых графов с четырьмя собственными значениями по их спектрам», Линейная алгебра и ее приложения , 3 : 461–482, doi : 10.1016/0024-3795(70)90037-6 , MR  0285432
4. Сандер, Торстен (2009), «Графы судоку являются целостными», Электронный журнал комбинаторики , 16 (1): Примечание 25, 7, MR  2529816