Abstract: Граф называется целочисленным, если все собственные значения его матрицы смежности являются целыми числами. В докладе даётся анализ текущего состояния современных исследований в рамках открытой задачи характеризации целочисленных графов. Постановка задачи восходит к пионерской работе Ф. Харари и А. Швенка, в которой авторы впервые задавались вопросом о существовании целочисленных графов . Первые результаты по характеризации целочисленных графов были получены для регулярных графов: среди кубических графов существует всего 13 целочисленных графов, а для 4-регулярных графов их полная характеризация в настоящий момент неизвестна, но известно, что в этом классе графов существуют целочисленные графы и мультиграфы диаграмм узлов с числом пересечений не более десяти. В докладе также обсуждается целочисленность деревьев, вершинно-транзитивных графов и графов Кэли. В частности, для графов Кэли на симметрической группе приводятся примеры целочисленных семейств графов и показывается связь с теорией представлений симметрической группы.

Cite: Константинова Е.В.
Целочисленные графы
Современные проблемы математики и её приложений 28-29 апр. 2023