RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретная математика // Архив

Дискрет. матем., 1999, том 11, выпуск 3, страницы 29–47 (Mi dm385)

О спектрах связных графов

С. В. Савченко


Аннотация: При помощи метода производящих функций изучены свойства спектров бесконечных связных графов вне некоторого критического круга. Радиус этого круга $\rho$ является обратной величиной от максимума $r(G)$ радиусов сходимости $r_v(G)$ производящих функций $\varphi_{G,v}(z)$ числа циклических маршрутов с запретом захода в начальную вершину $v$. Пусть $R(G)$ — радиус сходимости производящей функции числа циклических маршрутов с началом в фиксированной вершине (для связного графа он не зависит от выбора вершины). Известно, что если $r(G)>R(G)$, то для ориентированного графа $G$ и для любого $\varepsilon>0$ существует пространство $\ell^{1}(\mu^{(\varepsilon)})$, действие матрицы смежности $A(G)$ на котором определяет оператор с дискретным спектром вне круга радиуса $\rho+\varepsilon$. В работе собственные значения в этой области представлены как элементы множества $J(G)^{-1}$, где $J(G)$ — совокупность нулей функции $1-\varphi_{G,v}(z)$, соответствующей вершине $v$, для которой $r_v(G)=r(G)$. Геометрическая кратность каждого собственного значения из множества $J(G)^{-1}$ равна единице, а размер жордановой клетки совпадает с кратностью соответстующего нуля функции $1-\varphi_{G,v}(z)$. Спектры сходящихся к $G$ конечных подграфов вне круга радиуса $\rho+\varepsilon$ аппроксимируют собственные значения оператора $A(G)$. При условии $R(G)<r(G)$ спектр самосопряженного оператора на пространстве $\ell^{2}$, порожденного матрицей смежности неориентированного графа, в области $|\lambda|>r(G)^{-1}$ является дискретным и состоит не более, чем из двух точек. Одна из них является максимальной точкой спектра (число Перона-Фробениуса). Другая (при условии существования) расположена на отрицательной полуоси и характеризует размер максимальных двудольных частей графа (если она симметрична максимальной точке спектра относительно начала координат, то граф является двудольным).
Работа выполнена при поддержке INTAS–RFBR, грант 95–418.

УДК: 519.175

Статья поступила: 14.06.1996

DOI: 10.4213/dm385


 Англоязычная версия: Discrete Mathematics and Applications, 1999, 9:5, 503–522

Реферативные базы данных:


© МИАН, 2024