Let G be a graph with adjacency matrix A(G), and let D(G) be the diagonal matrix of the degrees of G. For any real number α∈[0,1], Nikiforov defined the Aα-matrix of G as
Aα(G)=αD(G)+(1−α)A(G).
The eigenvalues of the matrix Aα(G) form the Aα-spectrum of G. The Aα-spectral radius of G is the largest eigenvalue of Aα(G) denoted by ρα(G). In this paper, we propose the Aα−-matrix of G as
Aα−(G)=αD(G)+(α−1)A(G),0≤α≤1.
Let the Aα−-spectral radius of G be denoted by λα−(G), and let Sαβ(G) and Sα−β(G) be the sum of the βth powers of the Aα and Aα− eigenvalues of G, respectively. We determine the Aα−-spectra of some graphs and obtain some bounds of the Aα−-spectral radius. Moreover, we establish a relationship between the Aα-spectral radius and Aα−-spectral radius. Indeed, for α∈(12,1), we show that λα−≤ρα, and we prove that if G is connected, then the equality holds if and only if G is bipartite. Employing this relation, we obtain some upper bounds of λα−(G), and we prove that the Aα−-spectrum and Aα-spectrum are equal if and only if G is a bipartite connected graph. Furthermore, we generalize the relation established by S. Akbari et al. in (2010) as follows: for α∈[12,1), if 0<β≤1 or 2≤β≤3, then Sαβ(G)≥Sα−β(G), and if 1≤β≤2, then Sαβ(G)≤Sα−β(G), where the equality holds if and only if G is a bipartite graph such that β∉{1,2,3}.
Citation: Wafaa Fakieh, Zakeiah Alkhamisi, Hanaa Alashwali. On the Aα−-spectra of graphs and the relation between Aα- and Aα−-spectra[J]. AIMS Mathematics, 2024, 9(2): 4587-4603. doi: 10.3934/math.2024221
[1] | Zhen Lin . On the sum of the largest $ A_{\alpha} $-eigenvalues of graphs. AIMS Mathematics, 2022, 7(8): 15064-15074. doi: 10.3934/math.2022825 |
[2] | Bilal A. Rather, Fawad Ali, Nasim Ullah, Al-Sharef Mohammad, Anwarud Din, Sehra . $ A_{\alpha} $ matrix of commuting graphs of non-abelian groups. AIMS Mathematics, 2022, 7(8): 15436-15452. doi: 10.3934/math.2022845 |
[3] | Alfredo Sotelo-Pejerrey . Traces of certain integral operators related to the Riemann hypothesis. AIMS Mathematics, 2023, 8(10): 24971-24983. doi: 10.3934/math.20231274 |
[4] | Shuo Wang, Juan Liu, Xindong Zhang . Properties of solutions for fractional-order linear system with differential equations. AIMS Mathematics, 2022, 7(8): 15704-15713. doi: 10.3934/math.2022860 |
[5] | Efruz Özlem Mersin . Sturm's Theorem for Min matrices. AIMS Mathematics, 2023, 8(7): 17229-17245. doi: 10.3934/math.2023880 |
[6] | Samer Al-Ghour, Hanan Al-Saadi . Soft weakly connected sets and soft weakly connected components. AIMS Mathematics, 2024, 9(1): 1562-1575. doi: 10.3934/math.2024077 |
[7] | Meraj Ali Khan, Ali H. Alkhaldi, Mohd. Aquib . Estimation of eigenvalues for the $ \alpha $-Laplace operator on pseudo-slant submanifolds of generalized Sasakian space forms. AIMS Mathematics, 2022, 7(9): 16054-16066. doi: 10.3934/math.2022879 |
[8] | Jun He, Yan-Min Liu, Jun-Kang Tian, Ze-Rong Ren . A note on the inclusion sets for singular values. AIMS Mathematics, 2017, 2(2): 315-321. doi: 10.3934/Math.2017.2.315 |
[9] | Xiaofei Cao, Yuyue Huang, Xue Hua, Tingyu Zhao, Sanzhang Xu . Matrix inverses along the core parts of three matrix decompositions. AIMS Mathematics, 2023, 8(12): 30194-30208. doi: 10.3934/math.20231543 |
[10] | Xiaomei Zhang, Xiang Chen . Uniqueness of difference polynomials. AIMS Mathematics, 2021, 6(10): 10485-10494. doi: 10.3934/math.2021608 |
Let G be a graph with adjacency matrix A(G), and let D(G) be the diagonal matrix of the degrees of G. For any real number α∈[0,1], Nikiforov defined the Aα-matrix of G as
Aα(G)=αD(G)+(1−α)A(G).
The eigenvalues of the matrix Aα(G) form the Aα-spectrum of G. The Aα-spectral radius of G is the largest eigenvalue of Aα(G) denoted by ρα(G). In this paper, we propose the Aα−-matrix of G as
Aα−(G)=αD(G)+(α−1)A(G),0≤α≤1.
Let the Aα−-spectral radius of G be denoted by λα−(G), and let Sαβ(G) and Sα−β(G) be the sum of the βth powers of the Aα and Aα− eigenvalues of G, respectively. We determine the Aα−-spectra of some graphs and obtain some bounds of the Aα−-spectral radius. Moreover, we establish a relationship between the Aα-spectral radius and Aα−-spectral radius. Indeed, for α∈(12,1), we show that λα−≤ρα, and we prove that if G is connected, then the equality holds if and only if G is bipartite. Employing this relation, we obtain some upper bounds of λα−(G), and we prove that the Aα−-spectrum and Aα-spectrum are equal if and only if G is a bipartite connected graph. Furthermore, we generalize the relation established by S. Akbari et al. in (2010) as follows: for α∈[12,1), if 0<β≤1 or 2≤β≤3, then Sαβ(G)≥Sα−β(G), and if 1≤β≤2, then Sαβ(G)≤Sα−β(G), where the equality holds if and only if G is a bipartite graph such that β∉{1,2,3}.
Let
G=(V(G),E(G)) |
be a simple undirected graph on n vertices such that V(G) and E(G) denote the vertex set and edge set of G, respectively. Let V(G)={v1,v2,⋯,vn}, for vi∈V(G), and dG(vi)=d(vi)=di denotes the degree of vertex vi and the set of vertices adjacent to vi, denoted by N(vi), refers to the neighborhood of vi. The maximum and the minimum degree of G are denoted by Δ=Δ(G) and δ=δ(G), respectively. λ(M), λk(M) and λmin(M) denote the largest eigenvalue, the k-th largest eigenvalue, and the smallest eigenvalue of a matrix M, respectively. The set of all eigenvalues for a matrix M together with their multiplicities is called the M-spectrum. A real symmetric matrix M is called positive semidefinite if λmin(M)≥0. Denote by Kn, Pn, Cn and Ks,n−s the complete graph, path, cycle, and complete bipartite graph with n vertices, respectively. Let A(G) and D(G) be the adjacency matrix and the diagonal matrix of the degrees of G, respectively. The signless Laplacian Q(G) of G is defined as
Q(G)=D(G)+A(G). |
The Laplacian L(G) of G is defined as
L(G)=D(G)−A(G). |
We denote the eigenvalues of Q(G) and L(G) by ρk(G) and λk(G), respectively, where 1≤k≤n (we drop G when it is clear from the context). In particular, the largest eigenvalue of Q(G) is called the signless Laplacian spectral radius of G, denoted by ρ(G), and the largest eigenvalue of L(G) is called the Laplacian spectral radius of G, denoted by λ(G).
In [1], Nikiforov introduced the Aα-matrix of G, which is the convex linear combination of A(G) and D(G) defined by
Aα(G)=αD(G)+(1−α)A(G),0≤α≤1. |
Clearly,
A0(G)=A(G), A1(G)=D(G)and2A12(G)=Q(G). |
Thus, the matrix Aα(G) is a generalization of the adjacency matrix and the signless Laplacian matrix. The largest eigenvalue of Aα(G) is called the Aα-spectral radius of G, denoted by ρα(G). Nikiforov [1] had studied the matrix Aα(G), and he has investigated many properties on Aα(G), including bounds on the k-th largest (especially, the largest, the second largest, and the smallest) eigenvalue of Aα(G), the positive semidefiniteness of Aα(G), etc. From then on, the study of Aα-spectra and the Aα-spectral radius for the graph has attracted the attention of many researchers. In [2], Nikiforov et al. gave an upper bound of the spectral radius of Aα(TΔ), where TΔ is the tree of maximal degree Δ. Also, he obtained several bounds on the spectral radius of Aα of general graphs. The graphs with
λk(Aα(G))=αn−1,2≤k≤n |
had been characterized by Lin et al. in [3]. In [4], Guo and Zhou gave upper bounds for the Aα-spectral radius for some graphs under some conditions. Guo and Zhang [5]; obtained a sharp upper bound on the Aα-spectral radius for α∈[12,1), and proved that for two connected graphs G1 and G2, ρα(G1)>ρα(G2) under certain conditions. For further related studies, one may see [6,7,8].
The research on L(G) has shown that it is a remarkable matrix in many respects. Since; L(G) is just the difference between D(G) and A(G), then to understand to what extent each of the summands −A(G) and D(G) determines the properties of L(G), and motivated by the above works, we introduce the Aα−-matrix defined by
Aα−(G)=αD(G)+(α−1)A(G),0≤α≤1. | (1.1) |
Through our study, several facts indicate that the study of the Aα−(G) family is of a unique importance. First of all, obviously
A(G)=−A0−(G),D(G)=A1−(G)andL(G)=2A12−(G). |
Since A12−(G) is essentially equivalent to L(G), then the matrix Aα−(G) can be regarded as a generalization of the Laplacian matrix L(G). Since
A1(G)=A1−(G)=D(G); |
unless otherwise specified, we only consider the case of 0≤α<1 in this paper.
In this paper, we study some properties on Aα−(G) and obtain some bounds of the largest eigenvalue of Aα−(G). For the relation between the Q-spectrum and L-spectrum of a connected graph G, it is well known that G is bipartite if and only if Q(G) and L(G) has the same spectrum ([9, Proposition 1.3.10]), and we extend this relation on the Aα- and Aα−-spectrum. In [10], Akbari et al. proved that, for a graph G of order n and any real number β, if 0<β≤1 or 2≤β≤3, then
n∑k=1ρβk≥n∑k=1λβk; |
and if 1≤β≤2, then
n∑k=1ρβk≤n∑k=1λβk. |
In this work we present the relation between the sum of powers of Aα and Aα− eigenvalues, which is a generalization of the relation between the sum of powers of Q(G) and L(G) eigenvalues in [10].
The rest of this paper is organized as follows. In Section 2, we give some preliminaries and lemmas used later. In Section 3, we derive new basic properties of Aα−(G). In Section 4, we present the Aα−-spectra of the complete graphs and the complete split graphs. Section 5 gives some bounds of the largest eigenvalue of Aα−(G). In Section 6, we deduce the relation between the Aα- and Aα−-spectral radius. Finally, in Section 7, we prove the relation between the sum of powers of Aα and Aα− eigenvalues.
Although Weyl's inequalities have been known for almost a century (see, e.g., [11]), their equality case was first established by So in [12], and for convenience we state Weyl and So's complete theorem as follows:
Theorem 2.1. Let A and B be Hermitian matrices of order n, and let 1≤i≤n and 1≤j≤n. Then,
λi(A)+λj(B)≤λi+j−n(A+B),ifi+j≥n+1, | (2.1) |
λi(A)+λj(B)≥λi+j−1(A+B),ifi+j≤n+1. | (2.2) |
In either of these inequalities, the equality holds if and only if there exists a nonzero n-vector that is an eigenvector to each of the three eigenvalues involved.
A simplified version of (2.1) and (2.2) gives
λk(A)+λmin(B)≤λk(A+B)≤λk(A)+λ(B). | (2.3) |
We shall need the following lemmas for our new results.
Lemma 2.2. [3] Let G be a graph of order n. If e∈E(G) and α≥12, then,
ρi(Aα(G))≥ρi(Aα(G−e)),for1≤i≤n. |
Lemma 2.3. [13] Let B be a real symmetric nonnegative irreducible matrix and λ be the largest eigenvalue of B. Z∈Rn. If ZtBZ=λ and ‖Z‖=1, then BZ=λZ.
Lemma 2.4. [5] Let G be a connected graph with n≥4 vertices and m edges. If α∈[12,1), then,
ρα(G)≤max{αΔ(G),(1−α)(m−n−12)}+2α. |
Equality holds if and only if α=n−1n+1 and G=Kn.
For a graph G of order n, suppose that λ is an eigenvalue of Aα−(G) and x is an eigenvector of Aα−(G) with respect to λ. We use x(v) to denote the entry of x corresponding to the vertex v∈V(G). It is clear that the system of eigenequations for the matrix Aα−(G) is
λx(v)=αdG(v)x(v)+(α−1)∑u∈N(v)x(u). | (3.1) |
If G is a graph of order n with Aα−(G)=Aα−, and x is a real vector, the quadratic form ⟨Aα−x,x⟩ can be represented in several equivalent ways:
⟨Aα−x,x⟩=∑uv∈E(G)(αx(u)2+2(α−1)x(u)x(v)+αx(v)2), | (3.2) |
⟨Aα−x,x⟩=(2α−1)∑u∈V(G)x(u)2dG(u)+(1−α)∑uv∈E(G)(x(u)−x(v))2, | (3.3) |
⟨Aα−x,x⟩=α∑u∈V(G)x(u)2dG(u)+2(α−1)∑uv∈E(G)x(u)x(v). | (3.4) |
Each of these representations can be useful in proofs.
Now, we give some of the spectral properties of the Aα−-matrix. Let us call the largest eigenvalue of Aα−(G) the Aα−-spectral radius of G, and denote it as λα−(G). Let us also denote the smallest eigenvalue of Aα−(G) as μα−(G). Since Aα−(G) is a real symmetric matrix, and by using Rayleigh's principle, the following result holds:
Proposition 3.1. If α∈[0,1) and G is a graph of order n, then
λα−(G)=max‖x‖2=1⟨Aα−(G)x,x⟩andμα−(G)=min‖x‖2=1⟨Aα−(G)x,x⟩. | (3.5) |
Moreover, if x is a unit n-vector, then,
λα−(G)=⟨Aα−(G)x,x⟩ |
if and only if x is an eigenvector to λα−(G), and
μα−(G)=⟨Aα−(G)x,x⟩ |
if and only if x is an eigenvector to μα−(G).
By using these relations, the following result is evident:
Proposition 3.2. If α∈[0,1) and G is a graph, then
λα−(G)=max{λα−(H):HisacomponentofG}, |
μα−(G)=min{μα−(H):HisacomponentofG}. |
It is clear that if G is a d-regular graph of order n, then
Aα−(G)=αdIn+(α−1)A(G), |
and so there is a linear correspondence between the spectra of Aα−(G) and of A(G),
λk(Aα−(G))=αd+(α−1)λn−k+1(A(G)), 1≤k≤n. | (3.6) |
In particular, if k=n, then
μα−(G)=(2α−1)d |
for any α∈[0,1]. As a consequence of Weyl's inequality (2.3), the following result is immediate:
Proposition 3.3. If α∈[0,1] and G is a graph with
A(G)=AandAα−(G)=Aα−, |
then,
αδ+(α−1)λn−k+1(A)≤λk(Aα−)≤αΔ+(α−1)λn−k+1(A). |
An important property of the Laplacian L(G) is that it is positive semidefinite. This is certainly not true for Aα−(G) if α<12 and G is a regular graph, but if α≥12, then Aα−(G) is like L(G). We give this result in the following:
Proposition 3.4. If α≥12, and G is a graph, then Aα−(G) is positive semidefinite, and if α>12 and G has no isolated vertices, then Aα−(G) is positive definite. Moreover, if α<12 and G is a regular graph, then Aα−(G) is not positive semidefinite.
Proof. Let x be a nonzero vector. If α≤12, then for any edge uv∈E(G), we see that
⟨Aα−(G)x,x⟩≥(2α−1)(x(u)2+x(v)2)+(1−α)(x(u)−x(v))2≥0. | (3.7) |
Hence, Aα−(G) is positive semidefinite. Now, assume that G has no isolated vertices. Choose a vertex u with x(u)≠0 and let uv∈E(G). Then, (3.7) becomes a strict inequality, and so Aα−(G) is positive definite. Finally, suppose that G is a d−regular graph, α<12, and let A be its adjacency matrix, then λ(A)=d. Thus
μα−(G)=(2α−1)d<0. |
By the above proposition we get the following lemma which gives a relation between the Aα− eigenvalues of G and the Aα− eigenvalues of spanning subgraphs of G.
Lemma 3.5. Let G be a graph of order n and let α∈[12,1). If G′=G−e, where e∈E(G), then,
λi(G′)≤λi(G)for1≤i≤n. |
Proof. Let e=uv such that u,v∈V(G). It is easy to see that
Aα−(G)=Aα−(G′)+M, |
where M is the matrix of order n indexed by the vertices of G having (u,v)th and (v,u)th entries both equal to α−1, and the (u,u)th and (v,v)th entries both equal to α and all other entries equal to zero, hence M is an Aα−-matrix of a graph containing only one edge. Since α∈[12,1), then Aα−(G), Aα−(G′) and M are positive semidefinite and Weyl's inequalities (2.3) imply that λi(G′)≤λi(G).
Equality (3.6) and the fact the eigenvalues of A(Kn) are {n−1,−1,⋯,−1} give the spectrum of Aα−(Kn) as follows:
Proposition 4.1. The eigenvalues of Aα−(Kn) are
μα−(Kn)=(2α−1)(n−1)andλk(Aα−(Kn))=α(n−2)+1for1≤k≤n−1. |
If S⊆V(G), then we use G[S] to denote the subgraph of G induced by S. Recall that G[S] is an independent set if no two vertices of S are adjacent and G[S] is a clique if it is a complete subgraph of G. The graph Kr∨(n−r)K1 is called a complete split graph, denoted by CSr,n−r. The work in the following proposition is motivated by the proof of [3, Proposition 2.4].
Proposition 4.2. Let G be a graph with Aα−(G), and α∈[0,1). Let S⊆V(G) and |S|=k. Suppose that dG(u)=d for each vertex u∈S, and N(v)∖{w}=N(w)∖{v} for any two vertices v,w∈S. Then, we have the following statements:
(i) If G[S] is a clique, then α(d−1)+1 is an eigenvalue of Aα−(G) with multiplicity at least k−1.
(ii) If G[S] is an independent set, then αd is an eigenvalue of Aα−(G) with multiplicity at least k−1.
Proof. Let S={v1,v2,⋯,vk}. Clearly, d1=⋯=dk=d. Let z1,z2,⋯,zk−1 be vectors such that
{zi(v1)=1,zi(vi+1)=−1,zi(v)=0,if v∈V(G)∖{v1,vi+1}, |
for i=1,⋯,k−1. Assume that G[S] is a clique. It is easy to obtain that
Aα−(G)zi=(α(d1−1)+1,0,⋯,0,α(1−di)−1,0,⋯,0)′=(α(d−1)+1)zi, |
for i=1,⋯,k−1. Hence, α(d−1)+1 is an eigenvalue of Aα−(G) and z1,z2,⋯,zk−1 are eigenvectors of Aα−(G) corresponding to α(d−1)+1. In addition, since z1,z2,⋯,zk−1 are linearly independent, the multiplicity of α(d−1)+1 is at least k−1. Now, supposing that G[S] is an independent set, we have
Aα−(G)zi=(αd1,0,⋯,0,−αdi,0,⋯,0)′=αdzi, |
for i=1,⋯,k−1. Since z1,z2,⋯,zk−1 are linearly independent, it follows that αd is an eigenvalue of Aα−(G) with multiplicity at least k−1. Thus, the proof is completed.
Consider an n×n real symmetric matrix
S=(S11S12⋯S1tS21S22⋯S2t⋮⋮⋱⋮St1St2⋯Stt), |
whose rows and columns are partitioned according to a partitioning P1, P2, ⋯, Pt of {1,2,⋯,n}. The quotient matrix B of the matrix S is the t×t matrix whose entries are the average row sums of the blocks Sij of S. The partition is equitable if each block Sij of S has constant row sum.
Lemma 4.3. [14] Let B be an equitable quotient matrix of a symmetric real matrix S. If λ is an eigenvalue of B, then λ is also an eigenvalue of S.
Now, we can determine all Aα−-eigenvalues of CSr,n−r as follows:
Proposition 4.4. The Aα−-spectrum of CSr,n−r contains α(n−2)+1 with multiplicity r−1, αr with multiplicity n−r−1, and the remaining two Aα−-eigenvalues are
α(n+2(r−1))+1±√(α(n+2(r−1))+1)2+4r(1−2α)(n−r+α(r−1))2. | (4.1) |
Proof. We can write Aα−(CSr,n−r) as
Aα−(CSr,n−r)=((1−α)Jr,r+(αn−1)Ir(1−α)Jr,n−r(1−α)Jn−r,rαrIn−r,n−r). |
Then, the quotient matrix of Aα−(CSr,n−r) is equitable and it can be written in the form
B(Aα−(CSr,n−r))=((n−r)α+r−1(1−α)(n−r)(1−α)rαr). |
Thus, by Lemma 4.3, the eigenvalues of B(Aα−(CSr,n−r)) are eigenvalues of Aα−(CSr,n−r), and according to Proposition 4.2, we get the result.
In this section we give a few general bounds on λα−(G).
Proposition 5.1. Let G be a graph, with
Δ(G)=Δ, A(G)=AandD(G)=D. |
The following inequalities hold for λα−(G):
λα−(G)≥αΔ+(α−1)λ(A), | (5.1) |
λα−(G)≥(2α−1)λ(A). | (5.2) |
Proof. Inequality (5.1) follows by Weyl's inequalities (2.3) because
αΔ+(α−1)λ(A)=αλ(D)+(α−1)λ(A)=λ(αD)+λmin((α−1)A)≤λ(αD+(α−1)A)=λα−(G). |
To prove the inequality (5.2), let H be a component of G such that λ(A)=λ(A(H)). Let x be a positive unit vector to λ(A(H)). For every edge uv∈E(H), the AM-GM inequality implies that
2x(u)x(v)=2αx(u)x(v)+2(1−α)x(u)x(v)≤α(x(u)+x(v))22+2(1−α)x(u)x(v)=12(αx(u)2+2(α−1)x(u)x(v)+αx(v)2)+(3−2α)x(u)x(v). |
Summing this inequality over all edges uv∈E(H), and using (3.2), we get
λ(A)=λ(A(H))=⟨A(H)x,x⟩≤12⟨Aα−(H)x,x⟩+12(3−2α)λ(A); |
and then we get
2λ(A)−(3−2α)λ(A)≤⟨Aα−(H)x,x⟩≤λα−(G); |
hence
(2α−1)λ(A)≤λα−(G). |
Having inequality (5.2) in hand, if α≥12, then every lower bound of λ(A) gives a lower bound on λα−(G), but if α<12, then every upper bound of λ(A) gives a lower bound on λα−(G). We mention just two such bounds.
Corollary 5.2. Let G be a graph such that α≥12. If G is of order n and has m edges, then
λα−(G)≥(2α−1)2mn. |
Corollary 5.3. Let G be a connected graph such that α<12. If G is of order n and has m edges, then
λα−(G)≥(2α−1)√2m−n+1. |
Proposition 5.4. Let G be a graph of order n. If α∈(12,1], then,
λα−(G)≤α(n−2)+1. |
Moreover,
λα−(G)=α(n−2)+1 |
with multiplicity k−1 if G has k vertices of degree n−1.
Proof. Applying Lemma 3.5 leads to
λα−(G)≤λα−(Kn)=α(n−2)+1. |
If G has k vertices of degree n−1, then it follows from Proposition 4.2 that α(n−2)+1 is an eigenvalue of Aα−(G) with multiplicity at least k−1, and since
λα−(G)≤α(n−2)+1, |
we get
λα−(G)=α(n−2)+1 |
with multiplicity k−1.
Let G be a connected graph. Merris [15] pointed out λ(L(G))≤ρ(Q(G)), and the equality holds if G is a bipartite graph. In the next result, we generalize this result to the Aα−- and Aα-spectral radius of a connected graph.
Theorem 6.1. Let G be a graph of order n, α∈(0,1), λα−(G)=λα− and ρα(G)=ρα. We have λα−≤ρα. Moreover, if G is connected, then the equality holds if and only if G is bipartite.
Proof. Let
V(G)={v1,v2,⋯,vn}, x=(x1,x2,⋯,xn)t∈Rn |
be an arbitrary vector such that ‖x‖=1. Let
y=(y1,y2,⋯,yn)t∈Rn |
be a unit eigenvector of Aα−(G) belonging to λα− and
y′=(y′1,y′2,⋯,y′n)t∈Rn |
be a unit eigenvector of Aα(G) belonging to ρα. Let
|y|=(|y1|,|y2|,⋯,|yn|)t. |
First, we prove that λα−≤ρα.
λα−=maxxtAα−x=maxxt(αD+(α−1)A)x=max(αn∑i=1x2idi+2(α−1)∑vivj∈E(G)xixj)=ytAα−y=αn∑i=1y2idi+2(α−1)∑vivj∈E(G)yiyj |
and
ρα=maxxtAαx=maxxt(αD+(1−α)A)x=max(αn∑i=1x2idi+2(1−α)∑vivj∈E(G)xixj)=y′tAαy′=αn∑i=1y′i2di+2(1−α)∑vivj∈E(G)y′iy′j. |
Thus,
λα−=αn∑i=1y2idi+2(α−1)∑vivj∈E(G)yiyj≤αn∑i=1y2idi+2(1−α)∑vivj∈E(G)|yiyj|=|yt|Aα|y|≤maxxtAαx=ρα. | (6.1) |
Now, if G is bipartite, then the matrix Aα− and the matrix Aα are similar by a diagonal matrix D′ with diagonal entries ±1, that is, Aα=D′Aα−D′−1. Therefore, Aα− and Aα have the same spectrum, and thus we get λα−=ρα. Finally, when G is connected and λα−=ρα, all inequalities (6.1) must be equalities. By Lemma 2.3 and the equality
|yt|Aα|y|=ρα; |
we know that |y| is an eigenvector of Aα belonging to ρα. So, |y|=±y′. Using the Perron-Frobenius' theorem for Aα(G), we have y′>0, |y|=y′, and |yi|>0, i=1,2,⋯,n.
Since
αn∑i=1y2idi+2(α−1)∑vivj∈E(G)yiyj=αn∑i=1y2idi+2(1−α)∑vivj∈E(G)|yiyj|; |
we get
−∑vivj∈E(G)yiyj=∑vivj∈E(G)|yiyj|, |
hence, |yiyj|=−yiyj when vivj∈E(G). Therefore, yiyj<0 if vivj∈E(G).
Let
U={vi:yi>0}andW={vj:yj<0}. |
For each edge e=vivj, we have yiyj<0, one of the vertices of edge e is in U, and the other is in W. So, G is a bipartite graph.
Remark 6.2. If G is not bipartite and is not connected, and λα− is the largest eigenvalue of Aα− for a bipartite connected component of G, then the equality in Theorem 6.1 still holds.
Example 6.3. Take
G=C3∪C4. |
Then, G is not bipartite and not connected. Now, A14−(G) has a spectrum 2[1],1.25[2],0.5[2],−1[2] (where λ[i] means the eigenvalue λ is repeated i times in the spectrum). On the other hand, A14(G) has a spectrum 2[2],0.5[2],−0.25[2],−1[1]. Then, we have
λ14−(G)=ρ14(G)=2. |
Note that 2 is the largest eigenvalue of A14−(C4) as well.
Now, we introduce the relationship between the Aα−- and Aα-spectra of bipartite graphs, which is a generalization [9, Proposition 1.3.10], and it follows from the proof of the above theorem.
Corollary 6.4. Let G be a connected graph. Then, G is bipartite if and only if the Aα−-spectrum and Aα-spectrum are equal.
Remark 6.5. In fact, if G is bipartite and is not connected, the Aα−-spectrum still equals the Aα-spectrum.
Example 6.6. Take G=P3∪C4. Then G is bipartite and not connected. We have that A34−(G) has a spectrum 2[1],1.64039[1],1.5[2],1[1],0.75[1],0.609612[1]. In contrast, A34(G) has the same spectrum as A34−(G), although G is not connected.
According to Corollary 6.4 and [1, Propositions 38 and 39], we get the following two results:
Corollary 6.7. The Aα−-spectrum and the Aα-spectrum of the complete bipartite graph Ka,b are equal, that is, if a≥b≥1 and α∈(0,1), the eigenvalues of Aα−(Ka,b) are
λα−(Ka,b)=12(α(a+b)+√α2(a+b)2+4ab(1−2α)), |
μα−(Ka,b)=12(α(a+b)−√α2(a+b)2+4ab(1−2α)), |
λk(Aα−(Ka,b))=αafor1<k≤b, |
λk(Aα−(Ka,b))=αbforb<k<a+b. |
Corollary 6.8. The Aα−-spectrum and the Aα-spectrum of the star K1,n−1 are equal, that is, the eigenvalues of Aα−(K1,n−1) are
λα−(K1,n−1)=12(αn+√α2n2+4(n−1)(1−2α)), |
μα−(K1,n−1)=12(αn−√α2n2+4(n−1)(1−2α)), |
λk(Aα−(K1,n−1))=αfor1<k<n. |
Indeed, many practical results of Theorem 6.1 can be deduced, and here are some of them.
Proposition 6.9. Let G be a connected graph with n≥4 vertices and m edges. If α∈[12,1), then
λα−(G)<max{αΔ(G),(1−α)(m−n−12)}+2α. | (6.2) |
Proof. Let
λα−(G)=λα−andρα(G)=ρα. |
Then, Theorem 6.1 and Lemma 2.4 lead to
λα−≤max{αΔ(G),(1−α)(m−n−12)}+2α. | (6.3) |
Suppose that the equality in (6.3) holds, thus ρα=λα−, and so G is bipartite and
ρα=max{αΔ(G),(1−α)(m−n−12)}+2α. |
Therefore, by Lemma 2.4, G=Kn, and thus G is bipartite if and only if n=2, but n≥4, and hence the inequality is strict.
Theorem 6.1 and [2, Theorem 2] lead directly to the next result.
Proposition 6.10. If T is a tree of order n and α∈[0,1], then
λα−(T)≤nα+√n2α2+4(n−1)(1−2α)2. |
The equality holds if and only if T is the star K1,n−1.
By Theorem 6.1 and [1, Proposition 20], we get the next result.
Proposition 6.11. If G is a graph with no isolated vertices, then
λα−(G)≤maxu∈V(G){αd(u)+1−αd(u)∑uv∈E(G)d(v)}. |
If α∈(12,1) and G is connected, the equality holds if and only if G is a regular bipartite graph.
In this part we give two explicit expressions for the sums and the sum of squares of the eigenvalues of Aα− and Aα, considering [1, Propositions 34 and 35].
Proposition 6.12. If G is a graph of order n and has m edges, then
n∑i=1λi(Aα−(G))=n∑i=1λi(Aα(G))=trAα−(G)=trAα(G); |
where
n∑i=1λi(Aα−(G))=α∑u∈V(G)d(u)=2αm. |
A similar formula for the sum of the squares of the Aα− and Aα-eigenvalues is given as follows:
Proposition 6.13. If G is a graph of order n and has m edges, then
n∑i=1λ2i(Aα−(G))=n∑i=1λ2i(Aα(G))=trA2α−(G)=trA2α(G); |
where
n∑i=1λ2i(Aα−(G))=α2∑u∈V(G)d2(u)+2(1−α)2m. |
Proof. Let
Aα−=Aα−(G), A=A(G)andD=D(G). |
Calculating the square A2α− and taking its trace, we find that
trA2α−=tr(α2D2+(1−α)2A2+α(α−1)DA+α(α−1)AD)=α2trD2+(1−α)2trA2−α(1−α)trDA+α(α−1)trAD=α2∑u∈V(G)d2(u)+2(1−α)2m. |
Pirzada et al. [16] introduced the sum of the βth powers of the Aα eigenvalues of G as
Sαβ(G)=n∑i=1ρβi. |
Now, we have the notation
Sα−β(G)=n∑i=1λβi |
for the sum of the βth powers of the Aα− eigenvalues of G. The following theorem is a generalization [10, Theorem 2].
Theorem 7.1. Let G be a graph of order n>1, α∈[12,1), and let β be a real number.
(i) If 0<β≤1 or 2≤β≤3, then
Sαβ(G)≥Sα−β(G). |
(ii) If 1≤β≤2, then
Sαβ(G)≤Sα−β(G). |
For β∈(0,1)∪(2,3), the equality holds in (i) if and only if G is a bipartite graph. Moreover, for β∈(1,2), the equality holds in (ii) if and only if G is a bipartite graph.
Proof. We recall that, for any real number r, the binomial series
∞∑k=0(rk)xk |
converges to (1+x)r if |x|<1. This also remains true for x=−1 if r>0 (see, e.g., [17, p. 419]). By Lemma 3.5, we find that,
λα−(G)≤λα−(Kn)=α(n−2)+1andρα(G)≤ρα(Kn)=n−1. |
Since Aα is positive semidefinite when α∈[12,1), then if ρi>0, we have
|ρin−1|≤|n−1n−1|=|−1n|<1 |
and if ρi=0, we get
ρin−1=−1. |
Therefore,
Sαβ(G)nβ=(ρ1n)β+⋯+(ρnn)β=∞∑k=0(βk)(ρ1n−1)k+⋯+∞∑k=0(βk)(ρnn−1)k=∞∑k=0(βk)tr(1n(αD+(1−α)A)−I)k. |
Also, since Aα− is positive semidefinite when α∈[12,1), then if λi>0,
|λin−1|≤|α(n−2)+1n−1|=|(α−1)+1−2αn|<1 |
and if λi=0, we have
λin−1=−1. |
Thus, in a similar manner as above, we obtain that
Sα−β(G)nβ=∞∑k=0(βk)tr(1n(αD+(α−1)A)−I)k. |
We claim that
ifkis even, tr(αD+(1−α)A−nI)k≤tr(αD+(α−1)A−nI)k; |
ifkis odd, tr(αD+(1−α)A−nI)k≥tr(αD+(α−1)A−nI)k. |
When ((αD−nI)+(1−α)A)k and ((αD−nI)+(α−1)A)k are expanded in terms of the powers of αD−nI and (1−α)A, respectively, the terms appearing in both expansions, regardless of their signs, are the same. To prove this claim, we identify the sign of each term in both expansions. Consider the terms in the expansion of ((αD−nI)+(1−α)A)k, where there are exactly j factors equal to αD−nI, for some j=0,1,⋯,k. The sign of the trace for each of these terms is (−1)j or 0 because all entries of αD−nI and (1−α)A are non-positive and non-negative, respectively. On the other hand, in each term in the expansion of ((αD−nI)+(α−1)A)k all factors are matrices with non-positive entries, hence the sign of the trace of each term is (−1)k or 0. Therefore, the claim has been proven.
Now, note that if 0<β<1 or 2<β<3, then the sign of (βk) is (−1)k−1, except that (β2)>0, for 2<β<3. According to this, for 0<β<1 and every k,
(βk)tr(αD+(1−α)A−nI)k≥(βk)tr(αD+(α−1)A−nI)k. |
This inequality remains true for 2≤β≤3 as
tr(αD+(1−α)A−nI)2=tr(αD+(α−1)A−nI)2, |
since trA2α=trA2α−. Thus, Part (i) is proved. For 1<β<2, the sign of (βk) is (−1)k−1, except that (β1)>0. Since trAα=trAα−, we have
tr(αD+(1−α)A−nI)=tr(αD+(α−1)A−nI), |
and so part (ii) is similarly proved.
Now, we examine the equality case. Since Aα and Aα− are similar if G is bipartite, it follows that the equality holds in both (i) and (ii). Since for any positive integer i, trAi equals the total number of closed walks of length i in G, then if G is not bipartite, there exists an odd integer r such that trAr>0 (see [18, Lemma 2.5]). Hence,
tr(αD+(1−α)A−nI)r>tr(αD+(α−1)A−nI)r; |
and so the inequalities in both (i) and (ii) are strict.
We know that the Aα-spectra and Aα−-spectra of Kn are {(n−1)[1],(αn−1)[n−1]} and {((2α−1)(n−1))[1],(α(n−2)+1)[n−1]}, respectively. Therefore,
Sαβ(Kn)−Sα−β(Kn)=(n−1)β+(n−1)(αn−1)β−((2α−1)(n−1))β−(n−1)(α(n−2)+1)β. |
By Theorem 7.1 and based on our numerical experiments, we propose the following conjecture:
Conjecture 7.2. For every α∈(12,1) and each integer n≥3, we have
Sαβ(Kn)−Sα−β(Kn)≥0 |
for any β∈[0,1]∪[2,∞) and
Sαβ(Kn)−Sα−β(Kn)≤0 |
for any β∈(−∞,0)∪(1,2).
In this paper, we have introduced the Aα−-matrix of a graph G, which is a generalization of the Laplacian matrix L(G), and we have studied the basic properties of Aα−; and derived some bounds for its spectral radius. Furthermore, we have determined the Aα−-spectra for the complete graph and the complete split graph. Building upon previous results, we have extended findings related to the spectral radius of L(G) and Q(G) matrices to the Aα- and Aα−-spectral radius. Specifically, in Theorem 6.1, we have generalized Merris' [15] observation that λ(L(G))≤ρ(Q(G)) with equality holding for bipartite graphs. Additionally, we have extended the known relation that G is bipartite if and only if Q(G) and L(G) share the same spectrum, as demonstrated in Corollary 6.4. Finally, in Theorem 7.1; we have generalized a relation established by S. Akbari et al. in [10]; which relates the sum of powers of the eigenvalues of Q(G) and L(G). In conclusion, these findings have implications for various applications involving graph analysis.
The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.
The authors are grateful to the referees for their valuable suggestions and comments.
The authors declare no conflicts of interest.
[1] |
V. Nikiforov, Merging the A- and Q-spectral theories, Appl. Anal. Discrete Math., 11 (2017), 81–107. https://doi.org/10.2298/AADM1701081N doi: 10.2298/AADM1701081N
![]() |
[2] |
V. Nikiforov, G. Pastén, O. Rojo, R. L. Soto, On the Aα-spectra of trees, Linear Algebra Appl., 520 (2017), 286–305. https://doi.org/10.1016/j.laa.2017.01.029 doi: 10.1016/j.laa.2017.01.029
![]() |
[3] |
H. Lin, J. Xue, J. Shu, On the Aα-spectra of graphs, Linear Algebra Appl., 556 (2018), 210–219. https://doi.org/10.1016/j.laa.2018.07.003 doi: 10.1016/j.laa.2018.07.003
![]() |
[4] |
H. Guo, B. Zhou, On the α-spectral radius of graphs, Appl. Anal. Discrete Math., 14 (2020), 431–458. https://doi.org/10.2298/AADM180210022G doi: 10.2298/AADM180210022G
![]() |
[5] |
S. Guo, R. Zhang, Ordering graphs by their largest (least) Aα-eigenvalues, Linear Multilinear Algebra, 70 (2022), 7049–7056. https://doi.org/10.1080/03081087.2021.1981811 doi: 10.1080/03081087.2021.1981811
![]() |
[6] |
M. Basunia, I. Mahato, M. R. Kannan, On the Aα-spectra of some join graphs, Bull. Malays. Math. Sci. Soc., 44 (2021), 4269–4297. https://doi.org/10.1007/s40840-021-01166-z doi: 10.1007/s40840-021-01166-z
![]() |
[7] |
H. Lin, X. Huang, J. Xue, A note on the Aα-spectral radius of graphs, Linear Algebra Appl., 557 (2018), 430–437. https://doi.org/10.1016/j.laa.2018.08.008 doi: 10.1016/j.laa.2018.08.008
![]() |
[8] |
J. Wang, J. Wang, X. Liu, F. Belardo, Graphs whose Aα-spectral radius does not exceed 2, Discuss. Math. Graph Theory, 40 (2020), 677–690. https://doi.org/10.7151/dmgt.2288 doi: 10.7151/dmgt.2288
![]() |
[9] | A. E. Brouwer, W. H. Haemers, Spectra of graphs, Springer Science & Business Media, 2012. https://doi.org/10.1007/978-1-4614-1939-6 |
[10] |
S. Akbari, E. Ghorbani, J. H. Koolen, M. R. Oboudi, On sum of powers of the Laplacian and signless Laplacian eigenvalues of graphs, Electron. J. Comb., 2017 (2010), R115. https://doi.org/10.37236/387 doi: 10.37236/387
![]() |
[11] |
R. A. Horn, C. R. Johnson, Matrix analysis, 2 Eds., Cambridge University Press, 2012. https://doi.org/10.1017/CBO9781139020411 doi: 10.1017/CBO9781139020411
![]() |
[12] |
W. So, Commutativity and spectra of Hermitian matrices, Linear Algebra Appl., 212-213 (1994), 121–129. https://doi.org/10.1016/0024-3795(94)90399-9 doi: 10.1016/0024-3795(94)90399-9
![]() |
[13] |
J. Shu, Y. Hong, K. Ren, A sharp upper bound on the largest eigenvalue of the Laplacian matrix of a graph, Linear Algebra Appl., 347 (2002), 123–129. https://doi.org/10.1016/S0024-3795(01)00548-1 doi: 10.1016/S0024-3795(01)00548-1
![]() |
[14] |
L. You, M. Yan, W. So, W. Xi, On the spectrum of an equitable quotient matrix and its application, Linear Algebra Appl., 577 (2019), 21–40. https://doi.org/10.1016/j.laa.2019.04.013 doi: 10.1016/j.laa.2019.04.013
![]() |
[15] |
R. Merris, Laplacian matrices of graphs: a survey, Linear Algebra Appl., 197-198 (1994), 143–176. https://doi.org/10.1016/0024-3795(94)90486-3 doi: 10.1016/0024-3795(94)90486-3
![]() |
[16] |
S. Pirzada, B. A. Rather, R. Ul Shaban, T. A. Chishti, On the sum of the powers of Aα eigenvalues of graphs and Aα-energy like invariant, Bol. Soc. Paran. Mat., 40 (2022), 1–12. https://doi.org/10.5269/bspm.52469 doi: 10.5269/bspm.52469
![]() |
[17] | R. G. Bartle, The elements of real analysis, 2 Eds., John Wiley & Sons, Inc., 1976. |
[18] | N. Biggs, Algebraic graph theory, 2 Eds., Cambridge University Press, 1993. https://doi.org/10.1017/CBO9780511608704 |