Про суму беззнакових лапласiанiвських спектрiв графiв

Abstract

Для деякого простого графа G(VE) з n вершинами і m ребрами, множиною вершин V(G)=v1v2vn і множиною ребер E(G)=e1e2em , матриця суміжності A=(aij) графа G це (01)-квадратна матриця порядку n для якої елементи з індексом (ij) дорівнюють 1, якщо vi суміжна з vj і 0 у протилежному випадку. Нехай D(G)=diag(d1d2dn) --- діагональна матриця, асоційована з G, де di=deg(vi) для всіх i12n . Матриці L(G)=D(G)−A(G) і Q(G)=D(G)+A(G) називаються лапласіанівські і беззнакові лапласіанівські матриці, відповідно, а їх спектри (власні значення), відповідно --- лапласіанівським спектром (L-спектром) та беззнаковим лапласіанівським спектром (Q-спектром) графа G. Якщо 0=nn−11 є лапласіанівські власні значення G, Броувер припустив, що сума k найбільших лапласіанівських значень Sk(G) задовольняє Sk(G)=ki=1im+2k+1 і це припущення є все ще відкритим. Якщо q1q2qn --- беззнакові лапласіанівські власні значення графа G для 1kn, і нехай Sk+(G)=ki=1qi --- сума k найбільших беззнакових лапласіанівських власних значень G. Аналогічно до припущення Броувера, Асхраф та ін. припустили, що Sk+(G)m+2k+1 для всіх 1kn. Це припущення було підтверджено для деяких класів графів. Ми отримали верхнє обмеження для Sk+(G) в термінах клікових чисел , чисел покриття вершин і діаметр графа G. Зрештою, ми показали, що припущення виконується для широкої сім'ї графів.