Целый граф
Целый граф — это граф, спектр матрицы смежности (инвариант графа) которого состоит полностью из целых чисел. Другими словами, граф является целым графом, при условии, что все корни характеристического многочлена его матрицы смежности являются целыми числами[1].
Примеры
- Полный граф Kn является целым для всех n.
- Граф без рёбер является целым для всех n.
- Среди кубических симметричных графов целыми являются коммунальный граф, граф Петерсена, граф Науру и граф Дезарга.
- Целыми являются также граф Хигмана — Симса, граф Холла — Янко, граф Клебша, граф Хоффмана — Синглтона, граф Шрикханде и граф Хоффмана.
- Регулярный граф является периодическим тогда и только тогда, когда он целый.
- Граф регулярных блужданий, удовлетворяющий условиям идеальной передачи квантового состояния, является целым графом.
- Графы судоку, вершины которых представляют ячейки поля Судоку, а рёбра представляют ячейки, которые не должны быть равны, являются целыми графами[3].
Примечания
- 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.