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

Анотація

Для деякого простого графа $G(V,E)$ з $n$ вершинами і $m$ ребрами, множиною вершин $V(G)=\{v_1, v_2, \dots, v_n\}$ і множиною ребер $E(G)=\{e_1, e_2,\dots, e_m\}$, матриця суміжності $A=(a_{ij})$ графа $G$ $-$ це $(0, 1)$-квадратна матриця порядку $n$, для якої елементи з індексом $(i,j)$ дорівнюють 1, якщо $v_i$ суміжна з $v_j$ і 0 у протилежному випадку. Нехай $D(G)={diag}(d_1, d_2, \dots, d_n)$ $-$ діагональна матриця, асоційована з $G$, де $d_i=\deg(v_i),$ для всіх $i\in \{1,2,\dots,n\}$. Матриці $L(G)=D(G)-A(G)$ і $Q(G)=D(G)+A(G)$ називаються лапласіанівські і беззнакові лапласіанівські матриці, відповідно, а їх спектри (власні значення), відповідно $-$ лапласіанівським спектром ($L$-спектром) та беззнаковим лапласіанівським спектром ($Q$-спектром) графа $G$. Якщо $0=\mu_n\leq\mu_{n-1}\leq\cdots\leq\mu_1$ є лапласіанівські власні значення $G$, Броувер припустив, що сума $k$ найбільших лапласіанівських значень $S_{k}(G)$ задовольняє $S_{k}(G)=\sum\limits_{i=1}^{k}\mu_i\leq m+{k+1 \choose 2}$ і це припущення є все ще відкритим. Якщо $q_1,q_2, \dots, q_n$ $-$ беззнакові лапласіанівські власні значення графа $G$ для $1\leq k\leq n$, і нехай $S^{+}_{k}(G)=\sum_{i=1}^{k}q_i$ $-$ сума $k$ найбільших беззнакових лапласіанівських власних значень $G$. Аналогічно до припущення Броувера, Асхраф та ін. припустили, що $S^{+}_{k}(G)\leq m+{k+1 \choose 2}$ для всіх $1\leq k\leq n$. Це припущення було підтверджено для деяких класів графів. Ми отримали верхнє обмеження для $S^{+}_{k}(G)$ в термінах клікових чисел $\omega$, чисел покриття вершин $\tau$ і діаметра графа $G$. Зрештою, ми показали, що припущення виконується для широкої сім'ї графів.