Целый граф
Целый граф (целочисленный граф) — граф, спектр матрицы смежности (инвариант графа) которого состоит полностью из целых чисел. Другими словами, граф является целым графом, при условии, что все корни характеристического многочлена его матрицы смежности являются целыми числами[1]. Понятие ввели в 1974 году Харари и Швенк[2].
Примеры:
- полный граф является целым для всех ;
- граф без рёбер является целым для всех ;
- среди кубических симметричных графов целыми являются коммунальный граф, граф Петерсена, граф Науру и граф Дезарга;
- целыми являются также граф Хигмана — Симса, граф Холла — Янко, граф Клебша, граф Хоффмана — Синглтона, граф Шрикханде и граф Хоффмана;
- графы судоку, вершины которых представляют ячейки поля Судоку, а рёбра представляют ячейки, которые не должны быть равны, являются целыми графами[3].
Регулярный граф является периодическим[en] тогда и только тогда, когда он целый. Граф регулярных блужданий, удовлетворяющий условиям идеальной передачи квантового состояния[en], является целым графом.
ПримечанияПравить
- ↑ Weisstein, Eric W. Integral Graph (англ.) на сайте Wolfram MathWorld.
- ↑ Harary F., Schwenk A. J. Which Graphs have Integral Spectra? // Graphs and Combinatorics / R. Bari и F. Harary. — Berlin: Springer-Verlag, 1974. — С. 45—51.
- ↑ Torsten Sander. Sudoku graphs are integral // Electronic Journal of Combinatorics. — 2009. — Т. 16, вып. 1. — С. Note 25, 7.