On the sum of the largest $A_{\alpha}$-eigenvalues of graphs

1.   Introduction

Let $G$ be a simple undirected graph with vertex set $V(G) = \{v_1, v_2, \ldots, v_n\}$ and edge set $E(G)$. For $v_i\in V(G)$, $d_i = d_{G}(v_i)$ denotes the degree of vertex $v_i$, and $M_1 = M_1(G) = \sum_{i = 1}^{n}d_i^2$ is called the first Zagreb index. The minimum and the maximum degree of $G$ are denoted by $\delta(G)$ and $\Delta(G)$, or simply $\delta$ and $\Delta$, respectively. Denote by $K_n$, $C_n$ and $K_{s, \, n-s}$ the complete graph, cycle and complete bipartite graph with $n$ vertices, respectively. The positive inertia index $p = p(M)$ and the negative inertia index of a matrix $M$ are the number of positive and negative eigenvalues of $M$, respectively. For other undefined notations and terminology from graph theory, the readers are referred to ^[6].

For a graph $G$, $S_k(A(G))$ is the sum of the $k$ largest eigenvalues of adjacency matrix $A(G)$. Mohar ^[23] showed that $S_k(A(G))$ is at most $\frac{1}{2}(\sqrt{k}+1)n$. This bound is shown to be the best possible, in the sense that for every $k$ there exist graphs whose sum is $\frac{1}{2}(\sqrt{k}+\frac{1}{2})n-o(k^{-2/5})n$. Das et al. ^[11] proved an upper bound on $S_k(A(G))$ in terms of vertex number and negative inertia index. Let $L(G) = D(G)-A(G)$ be the Laplacian matrix of a graph $G$. Based on the famous Grone-Merris-Bai theorem ^[3,14], Brouwer et al. ^[5] proposed the following conjecture.

Conjecture 1.1. (Brouwer's conjecture) Let $G$ be a graph with $n$ vertices and $e(G)$ edges. For $1\leq k \leq n$, we have

Inspired by Brouwer's conjecture, Ashraf et al. ^[2] proposed a similar conjecture as follows.

Conjecture 1.2. ^[2] Let $G$ be a graph with $n$ vertices and $e(G)$ edges. For $1\leq k \leq n$, we have

where $Q(G) = D(G)+A(G)$ is called the signless Laplacian matrix of $G$.

The above two conjectures have been proven to be correct for all graphs with at most ten vertices ^[2], all graphs with $k = 1, 2, n-2, n-1, n$ ^[2,7], regular graphs ^[2], trees ^[17], unicyclic graphs ^[31,32], bicyclic graphs ^[31,32], tricyclic graphs ^[31,32] and so on. In particular, Haemers et al. ^[17] proved that $S_k(L(T))\leq e(T)+2k-1$ when $T$ is a tree with $n$ vertices.

Another motivation to study $S_k(A(G))$ and $S_k(Q(G))$ came from the energy $\varepsilon(A(G))$ and signless Laplacian energy $\varepsilon(Q(G))$ of a graph $G$, which is very popular in mathematical chemistry. Let $G$ be a graph with $n$ vertices, $m$ edges and the positive inertia index $p$. Then we have

and

where $\lambda_k(M)$ is the $k$-th largest eigenvalue of the matrix $M$. Thus, $S_k(A(G))$ and $S_k(Q(G))$ are close relation with the energy and signless Laplacian energy, respectively. For more details in this field, we refer the reader to ^[1,11,13,22]. In addition, $S_k(A(G))$ is related to Ky Fan norms of graphs introduced by Nikiforov ^[25], which are a fundamental matrix parameter anyway.

For any real $\alpha \in[0, 1]$, Nikiforov ^[24] defined the matrix $A_{\alpha}(G)$ as

where $D(G)$ is the diagonal matrix of its vertex degrees, and $A(G)$ is the adjacency matrix. It is easy to see that $A_{0}(G) = A(G)$ and $2A_{1/2}(G) = Q(G)$. The new matrix $A_{\alpha}(G)$ not only can underpin a unified theory of $A(G)$ and $Q(G)$, but it also brings many new interesting problems, see ^{[18,19,20,24,26]}. This matrix has recently attracted the attention of many researchers, and there are several research papers published recently, see ^[4,20,21,29] and the references therein.

Motivated by the above works, we study the sum of the $k$ largest eigenvalues of $A_{\alpha}(G)$. Since $S_k(A_{0}(G)) = S_k(A(G))$ and $2S_k(A_{1/2}(G)) = S_k(Q(G))$, $S_k(A_{\alpha}(G))$ can be regard as a common generalization of $S_k(A(G))$ and $S_k(Q(G))$. Moreover, if $G$ is a graph with $n$ vertices and $m$ edges, then

where $\varepsilon_{\alpha}(G)$ is the $\alpha$-energy of $G$ defined by Guo and Zhou ^[15]. Thus, $S_k(A_{\alpha}(G))$ is a close relation with the $\alpha$-energy of $G$. It is not difficult to see that $\varepsilon_{0}(G) = \varepsilon(A(G))$ and $2\varepsilon_{1/2}(G) = \varepsilon(Q(G))$.

In this paper, we obtain some upper and lower bounds on the sum of the $k$ largest eigenvalues of $A_{\alpha}(G)$, which extend the results of $S_k(A(G))$ and $S_k(Q(G))$. In particular, we give new bounds on the energy of graphs in terms of the positive inertia index and the first Zagreb index. In addition, some graph operations on $S_k(A_{\alpha}(G))$ are presented, which provides new bounds for the energy of graph operations.

The remainder of this paper is organized as follows. In Section 2, we recall some useful notions and lemmas used further. In Section 3, some upper bounds on $S_k(A_{\alpha}(G))$ are obtained in terms of $A_{\alpha}$-spectral radius and the first Zagreb index. Similarly to Conjecture 2, a conjecture is proposed for $\frac{1}{2}\leq \alpha < 1$. In Section 4, the line graph and the square of graphs on $S_k(A_{\alpha}(G))$ are presented.

2.   Preliminaries

The line graph $\mathcal{L}(G)$ is the graph whose vertex set is the edges in $G$, where two vertices are adjacent if the corresponding edges in $G$ have a common vertex. The square $G^2$ of a graph $G$ is a graph with the same set of vertices as $G$ such that two vertices are adjacent in $G^2$ if and only if their distance in $G$ is at most $2$. The second smallest eigenvalue of the Laplacian of a graph $G$, best-known as the algebraic connectivity of $G$, is denoted by $a(G)$.

Lemma 2.1. ^[12] Let $M$ and $N$ be two real symmetric matrices of order $n$. Then we have

for any $1\leq k \leq n$.

Lemma 2.2. ^[24] Let $G$ be a graph with $n$ vertices. Then we have

Lemma 2.3. ^[9] Let $G$ be a graph with $n$ vertices and $m\geq 1$ edges. Then, $\lambda_i(Q(G)) = \lambda_i(A(\mathcal{L}(G)))+2$, $i = 1, 2, \ldots, s$, where $s = \min\{n, m\}$.Further, if $m > n$, we have $\lambda_i(A(\mathcal{L}(G))) = -2$ for $i\geq n+1$, and if $n > m$, we have $\lambda_i(Q(G)) = 0$ for $i\geq m+1$.

Lemma 2.4. ^[8] For any $C_3$-free and $C_4$-free graph $G$, $A(G^2) = A^2(G)-L(G)$.

3.   Bounds on the sum of the largest $A_{\alpha}$-eigenvalues

Theorem 3.1. Let $G$ be a graph with $n$ vertices.

(i) If $0\leq \alpha < \frac{1}{2}$, then

for $1\leq k \leq n$.

(ii) If $\frac{1}{2}\leq \alpha < 1$, then

for $1\leq k \leq n$.

If $G$ is $r$-regular, then the equality in the above inequalities must hold.

Proof. (i) Since $A_{\alpha}(G) = \alpha Q(G)+(1-2\alpha)A(G)$ for $0\leq \alpha < \frac{1}{2}$, by Lemma 2.1, we have

If $0\leq \alpha < \frac{1}{2}$, then $\frac{1}{2}\leq 1-\alpha \leq 1$. Note that $A_{1-\alpha}(G) = \alpha Q(G)+(1-2\alpha)D(G)$. Since $A_{\alpha}(G)+A_{1-\alpha}(G) = Q(G)$, by Lemma 2.1, we have

(ii) Since $A_{\alpha}(G) = (1-\alpha) Q(G)+(2\alpha-1)D(G)$ for $\frac{1}{2}\leq \alpha < 1$, by Lemma 2.1, we have

If $\frac{1}{2}\leq \alpha \leq 1$, then $0 \leq 1-\alpha \leq \frac{1}{2}$. Note that $A_{1-\alpha}(G) = (1-\alpha) Q(G)+(2\alpha-1)A(G)$. Since $A_{\alpha}(G)+A_{1-\alpha}(G) = Q(G)$, by Lemma 2.1, we have

If $G$ is $r$-regular, from ^[24], we have $S_k(A_{\alpha}(G)) = \alpha k r+(1-\alpha)S_k(A(G))$ and $S_k(Q(G)) = kr+S_k(A(G))$. Thus, the two above equations hold. This completes the proof.

It is well known that the spectrum of any symmetric matrix majorizes its main diagonal, that is, $S_k(Q(G))\geq S_k(D(G))$, and by Theorem 3.1, we have the following corollary.

Corollary 3.1. Let $G$ be a graph with $n$ vertices. If $\frac{1}{2}\leq \alpha < 1$, then

for $1\leq k \leq n$.

From Corollary 3.1 and Conjecture 1.1, we give a new conjecture.

Conjecture 3.1. Let $G$ be a graph with $n$ vertices and $e(G)$ edges. If $\frac{1}{2}\leq \alpha < 1$, then

for $1\leq k \leq n$.

Theorem 3.2. Let $G$ be a graph with $n$ vertices and $m$ edges. If $0\leq \alpha < 1$, then

where $\Upsilon = (n-1)(\alpha^2M_1+2m(1-\alpha)^2-\lambda_1^2(A_{\alpha}(G)))-(2\alpha m-\lambda_1(A_{\alpha}(G)))^2$. The equality holds for $k = 1$. Moreover, the equality holds if and only if $\lambda_2(A_{\alpha}(G)) = \cdots = \lambda_k(A_{\alpha}(G))$ and $\lambda_{k+1}(A_{\alpha}(G)) = \cdots = \lambda_n(A_{\alpha}(G))$ for $k\geq 2$.

Proof. Let $\lambda_i(A_{\alpha}(G)) = \lambda_i$ and $S_k(A_{\alpha}(G)) = S_k$ for $i = 1, 2, \ldots, n$. Since $\sum\limits_{i = 1}^{n}\lambda_i = 2\alpha m$, $\sum\limits_{i = 1}^{n}\lambda_i^2 = \alpha^2M_1+2m(1-\alpha)^2$, and by the Cauchy-Schwarz inequality, we have

with equality if and only if $\lambda_2 = \cdots = \lambda_k$ and $\lambda_{k+1} = \cdots = \lambda_n$ for $k\geq 2$. Thus,

that is,

where

This completes the proof.

Remark 3.1. If the equality in $(3.1)$ holds, then this implies that $G$ has at most three distinct $A_{\alpha}$-eigenvalues. If $G$ is a connected graph with two distinct $A_{\alpha}$-eigenvalues, then $G\cong K_n$. Clearly, the equality in $(3.1)$ holds for $K_n$. If $G$ is a graph with three distinct $A_{\alpha}$-eigenvalues, then we refer to ^[30].

Corollary 3.2. Let $G$ be a graph with $n$ vertices and $m$ edges. If $p$ is the positive inertia index of $A(G)$, then

The equality holds for $K_n$ and $K_{s, \, t}$ ($s+t = n$).

Remark 3.2. There are many graphs such that the equality in $(3.2)$ holds, we may refer to ^[10,28].

Let $\alpha_0$ be the smallest $\alpha$ such that $A_{\alpha}(G)$ is positive semidefinite for $\alpha_0\leq \alpha \leq 1$. Recently, Nikiforov et al. ^[27] and Brondani et al. ^[4] found $\alpha_0$ for some special classes of graphs.

Theorem 3.3. Let $0\leq \alpha < \alpha_0$ and $G$ be a graph with $n$ vertices and $m$ edges.Then we have

with equality if and only if $|\lambda_{k+1}(A_{\alpha}(G))| = \cdots = |\lambda_{n}(A_{\alpha}(G))| = \frac{2m(1-\alpha)^2+\alpha^2M_1}{2}\sqrt{\frac{n}{(n-k)M_1}}$.

Proof. By Lemma 2.2, we have $\lambda_1(A_{\alpha}(G))\geq \sqrt{\frac{M_1}{n}}$. We assume that

in which case

This implies that

which is a contradiction. Thus,

By the Cauchy-Schwarz inequality, we have

with equality if and only if $|\lambda_{k+1}(A_{\alpha}(G))| = \cdots = |\lambda_{n}(A_{\alpha}(G))| = \frac{2m(1-\alpha)^2+\alpha^2M_1}{2}\sqrt{\frac{n}{(n-k)M_1}}$. This completes the proof.

Corollary 3.3. Let $G$ be a graph with $n$ vertices and $m$ edges. If $p$ is the positive inertia index of $A(G)$, then

with equality if and only if $|\lambda_{p+1}(A(G))| = \cdots = |\lambda_{n}(A(G))| = m\sqrt{\frac{n}{(n-p)M_1}}$.

Let $M$ be a real symmetric partitioned matrix of order $n$ described in the following block form:

where the diagonal blocks $M_{ii}$ are $n_i\times n_i$ matrices for any $i \in \{1, 2, \ldots, t\}$ and $n = n_1+\cdots+n_t$. For any $i, j \in \{1, 2, \ldots, t\}$, let $b_{ij}$ denote the average row sum of $M_{ij}$, i.e., $b_{ij}$ is the sum of all entries in $M_{ij}$ divided by the number of rows. Then, $\mathcal{B}(M) = (b_{ij})$ (or denoted simply by $\mathcal{B}$) is called the quotient matrix of $M$.

Lemma 3.1. ^[16] Let $M$ be a symmetric partitioned matrix of order $n$ with eigenvalues $\xi_1\geq \xi_2 \geq \cdots \geq \xi_n$, and let $\mathcal{B}$ be its quotient matrix with eigenvalues $\eta_1\geq \eta_2 \geq \cdots \geq \eta_r$ and $n > r$. Then, $\xi_i \geq \eta_i \geq \xi_{n-r+i}$for $i = 1, 2, \ldots, r$.

Let $\mathcal{B}$ be the quotient matrix of $A_{\alpha}(G)$ corresponding to the partition for the color classes of $G$. Then, the following corollary is immediate.

Corollary 3.4. Let $G$ be a connected graph with $n$ vertices, $m$ edges, chromatic number $\chi$ and independence number $\theta$. If $0\leq \alpha < 1$, then

Theorem 3.4. Let $0\leq \alpha < 1$ and $G$ be a connected graph with $n$ vertices and $m$ edges. For any given vertices subset $U = \{u_1, \ldots, u_{k-1}\}$ with $1\leq k \leq n$,

where $\partial(U, V(G)\backslash U)$ is the set of edges which connect vertices in $U$ with vertices in $V(G)\backslash U$.

Proof. If $2\leq k \leq n$, then the quotient matrix of $A_{\alpha}(G)$ corresponding to the partition $V(G) = (\bigcup\limits_{x\in U}\{x\})\cup (V(G)\backslash U)$ of $G$ is

where $A_{\alpha}(U)$ is the principal submatrix of $A_{\alpha}(G)$. By Lemma 3.1, we have

If $k = 1$, then $U$ is an empty set. Thus, $\sum\limits_{u\in U}d_u = 0$ and $|\partial(U, V(G)\backslash U)| = 0$. Taking $X = (1, \ldots, 1)^T$, by Rayleigh's principle, we have

Therefore, the above inequality still holds for $k = 1$. This completes the proof.

Corollary 3.5. Let $G$ be a connected graph with $n$ vertices, $m$ edges and the positive inertia index $p$. Then we have

4.   On the sum of the largest $A_{\alpha}$-eigenvalues of graph operations

Theorem 4.1. Let $G$ be a graph with $n$ vertices and $m\geq 1$ edges. Then we have

for $1\leq k \leq s$, where $s = \min\{n, m\}$. If $m > n$, then

for $n+1\leq k \leq m$.

Proof. If a vertex $w$ is in one-to-one correspondence with the edge $uv$ of the graph $G$, then $d_{\mathcal{L}(G)}(w) = d_G(u)+d_G(v)-2$. By Lemmas 2.1 and 2.3, we have

for $1\leq k \leq s$, where $s = \min\{n, m\}$. If $m > n$, then we have

for $n+1\leq k \leq m$. This completes the proof.

By the special cases of Conjecture 1.2 and Theorem 4.1, we have the following corollaries.

Corollary 4.1. If $T$ is a tree with $n$ vertices, then $S_{k}(A_{\alpha}(\mathcal{L}(T)))\leq 2k\alpha(\Delta-1)+(1-\alpha)(n-2)$ for $1\leq k \leq n-1$. If $U$ is a unicyclic graph with $n$ vertices, then $S_{k}(A_{\alpha}(\mathcal{L}(U)))\leq 2k(\alpha \Delta-1)+(1-\alpha)(n+\frac{k^2+k}{2})$ for $1\leq k \leq n$. If $B$ is a bicyclic graph with $n$ vertices, then $S_{k}(A_{\alpha}(\mathcal{L}(B)))\leq 2k(\alpha \Delta-1)+(1-\alpha)(n+1+\frac{k^2+k}{2})$ for $1\leq k \leq n$.

Corollary 4.2. If $T$ is a tree with $n$ vertices, then $\mathcal{E}(\mathcal{L}(T))\leq 2(n-2)$. If $U$ is a unicyclic graph with $n$ vertices, then $\mathcal{E}(\mathcal{L}(U)))\leq 2n+p^2-3p$. If $B$ is a bicyclic graph with $n$ vertices, then $\mathcal{E}(\mathcal{L}(B))\leq 2n+p^2-3p+2$.

Theorem 4.2. Let $G$ be a $C_3$-free and $C_4$-free graph with $n$ vertices, $m$ edges and the algebraic connectivity $a(G)$. If $0\leq \alpha \leq 1$, then

Proof. By Lemma 2.2, we have

Since $\sum\limits_{u \in V(G^2)}d_u = M_1(G)$, by Lemmas 2.1 and 2.4, we have

This completes the proof.

Corollary 4.3. Let $G$ be a $C_3$-free and $C_4$-free graph with $n$ vertices, $m$ edges and the algebraic connectivity $a(G)$. If $p$ is the positive inertia index of $A(G^2)$, then

5.   Conclusions

In this paper, we study the sum of the $k$ largest eigenvalues of the $A_{\alpha}$-matrix of a graph, which not only extends the results of the sum of the $k$ largest eigenvalues of the adjacency matrix and signless Laplacian matrix, but it also gives new bounds on graph energy.

Acknowledgments

This work was supported by the National Natural Science Foundation of China (No. 12071411).

Conflict of interest

The authors declare no conflicts of interest.