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

Ключові слова:
беззнакові лапласіанівські спектри, припущення Броувера, клікові числа, числа покриття вершин, діаметрАнотація
Для деякого простого графа G(V,E) з n вершинами і m ребрами, множиною вершин V(G)={v1,v2,…,vn} і множиною ребер E(G)={e1,e2,…,em}, матриця суміжності A=(aij) графа G − це (0,1)-квадратна матриця порядку n, для якої елементи з індексом (i,j) дорівнюють 1, якщо vi суміжна з vj і 0 у протилежному випадку. Нехай D(G)=diag(d1,d2,…,dn) − діагональна матриця, асоційована з G, де di=deg(vi), для всіх i∈{1,2,…,n}. Матриці L(G)=D(G)−A(G) і Q(G)=D(G)+A(G) називаються лапласіанівські і беззнакові лапласіанівські матриці, відповідно, а їх спектри (власні значення), відповідно − лапласіанівським спектром (L-спектром) та беззнаковим лапласіанівським спектром (Q-спектром) графа G. Якщо 0=μn≤μn−1≤⋯≤μ1 є лапласіанівські власні значення G, Броувер припустив, що сума k найбільших лапласіанівських значень Sk(G) задовольняє Sk(G)=k∑i=1μi≤m+(k+12) і це припущення є все ще відкритим. Якщо q1,q2,…,qn − беззнакові лапласіанівські власні значення графа G для 1≤k≤n, і нехай S+k(G)=∑ki=1qi − сума k найбільших беззнакових лапласіанівських власних значень G. Аналогічно до припущення Броувера, Асхраф та ін. припустили, що S+k(G)≤m+(k+12) для всіх 1≤k≤n. Це припущення було підтверджено для деяких класів графів. Ми отримали верхнє обмеження для S+k(G) в термінах клікових чисел ω, чисел покриття вершин τ і діаметра графа G. Зрештою, ми показали, що припущення виконується для широкої сім'ї графів.