О спектрах связных графов
С. В. Савченко
Аннотация:
При помощи метода производящих функций изучены свойства спектров бесконечных связных графов вне некоторого критического круга. Радиус этого круга
$\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