Bounding the sum of the largest signless Laplacian eigenvalues of a graph Aida AbiadLeonardo de LimaSina Kalantarzadeh

2025-04-30 0 0 388.64KB 16 页 10玖币

侵权投诉

Bounding the sum of the largest

signless Laplacian eigenvalues of a graph

Aida Abiad ∗†‡ Leonardo de Lima§Sina Kalantarzadeh¶

Mona Mohammadi‖Carla Oliveira∗∗

Abstract

We show several sharp upper and lower bounds for the sum of the largest

eigenvalues of the signless Laplacian matrix. These bounds improve and extend

previously known bounds.

AMS classiﬁcation: 05C50, 05C35

1 Introduction

Consider G= (V, E) to be a simple graph with nvertices such that |V|=n. Let N(vi)

be the set of neighbors of a vertex vi∈Vand |N(vi)|its cardinality. The sequence

degree of Gis denoted by d(G)=(d1(G), d2(G), . . . , dn(G)) ,such that di(G) = |N(vi)|

is the degree of the vertex vi∈Vand d1(G)≥d2(G)≥ ··· ≥ dn(G).The Laplacian

matrix of Gis deﬁned as L=D−A, where Dis the diagonal matrix of the vertex

degrees and Ais the adjacency matrix of G. The signless Laplacian matrix (or Q-

matrix), deﬁned as Q=A+D, has received a lot of attention, see, e.g., [6,7,8].

The eigenvalues of Land Qare denoted as λ1(G)≥λ2(G)≥ ··· ≥ λn(G) = 0 and

q1(G)≥q2(G)≥ ··· ≥ qn(G), respectively. For simplicity, the eigenvalues of Qand L

are called here as Q−eigenvalues and L−eigenvalues of G, respectively.

Using Schur’s inequality [17], it is known that

i=1

λi(G)≥

i=1

di(G) (1)

∗Department of Mathematics and Computer Science, Eindhoven University of Technology, The

Netherlands

†Department of Mathematics: Analysis, Logic and Discrete Mathematics, Ghent University, Bel-

gium

‡Department of Mathematics and Data Science, Vrije Universiteit Brussel, Belgium

(a.abiad.monge@tue.nl)

§Graduate Program in Mathematics, Federal University of Parana, Curitiba, Brazil

(leonardo.delima@ufpr.br)

¶Sharif University of Technology, Iran (sinakalantarzadehhh@yahoo.com)

‖Sharif University of Technology, Iran (mona.mohammadi78@gmail.com)

∗∗Department of Mathematical, National School of Statistical Sciences, Rio de Janeiro, Brazil

(carla.oliveira@ibge.gov.br)

arXiv:2210.03635v1 [math.CO] 7 Oct 2022

and m

i=1

qi(G)≥

i=1

di(G) (2)

for 1 ≤m≤n. Note that if m=n, we have equality in (1) and (2), because both

terms correspond to the trace of Land Q, respectively. An improvement of (1) is due

to Grone [11], who proved that if Gis connected and k < n then,

i=1

λi(G)≥

i=1

di(G)+1.(3)

The ﬁrst author, Fiol, Haemers and Perarnau [1] showed a generalization and a variation

of (3), as well as an extension of some inequalities by Grone and Merris [12].

There have been some results bounding the sum of the two largest signless Laplacian

eigenvalues, see for example [2], [10] and [19]. Cvetkovi´c, Rowlinson and Simi´c [4] proved

that q1(G)≥d1(G) + 1. After, Das [9] showed that q2(G)≥d2(G)−1.An immediate

lower bound is q1(G) + q2(G)≥d1(G) + d2(G) (note that Schur’s inequality can also

be used to obtain the same result).

In this paper, we use a mix of two types of interlacing (Cauchy and quotient matrix)

to obtain several sharp lower and upper bounds on the sum of the largest signless

Laplacian eigenvalues. In particular, we show a lower bound for q1(G) + q2(G) and

characterize the case of equality. This bound improves previously known bounds. We

also show several sharp bounds for the sum of the largest Q-eigenvalues, providing a Q-

analog of Grone’s inequality (3). The paper is organized such that preliminary results

are presented in Section 2, and Sections 3and 4are devoted to the main results.

2 Preliminaries

Some of our proofs use a classical result in matrix theory, the Cauchy interlacing theo-

rem (see for instance [15, Theorem 4.3.8], [14]).

Theorem 1 (Interlacing Theorem) ([14]) Let Abe a real symmetric n×nmatrix

with eigenvalues λ1≥ ··· ≥ λn. For some m<n, let Sbe a real n×mmatrix with

orthonormal columns, S>S=I, and consider the matrix B=S>AS, with eigenvalues

µ1≥ ··· ≥ µm.

(i)The eigenvalues of Binterlace those of A, that is,

λi≥µi≥λn−m+i, i = 1, . . . , m, (4)

(ii)If the interlacing is tight, that is, if exist an integer k∈[0, m]such that λi=µi,

for i= 1, . . . , k, and µi=λn−m+i, for i=k+ 1, . . . , m, then SB =AS.

Two interesting types of eigenvalue interlacing appear depending on the choice of

B: when Bis a principal submatrix of A(the so-called Cauchy interlacing), and when

Bis the quotient matrix of a certain partition of A. Our proofs in Section 4will require

a novel mix of the two types of eigenvalue interlacing.

The Cauchy interlacing theorem for the signless Laplacian matrix holds in a spe-

ciﬁc way. In [18, Theorem 2.6], for a vertex v∈V, the authors proved that the

Q−eigenvalues of Gand G−vinterlace, where G−vis a graph obtain from Gremov-

ing the vertex v:

Theorem 2 ([18]) Let Gbe a graph of order nand v∈V. Then for i= 1, . . . , n −1,

qi+1(G)−1≤qi(G−v)≤qi(G),

where the right inequality holds if and only if vis an isolated vertex.

Cvetkovi´c et al. in [5] presented an edge removal version of the Cauchy interlacing

theorem for the Q-eigenvalues by using line graphs:

Theorem 3 ([5]) Let Gbe a graph on nvertices and let ebe an edge of G. Let

q1≥q2≥ ··· ≥ qnand s1≥s2≥ ··· ≥ snbe the Q- eigenvalues of Gand G−e,

respectively. Then

0≤sn≤qn≤ ··· ≤ s2≤q2≤s1≤q1.

It turns out that the Cauchy interlacing theorem also holds for the Laplacian matrix

of Gas showed by Godsil and Royle [13, Theorem 13.6.2]:

Theorem 4 ([13]) Let Gbe a graph on nvertices and let e∈Ebe an edge of G. The

L−eigenvalues of Gand H=G−einterlace, that is,

λ1(G)≥λ1(H)≥ ··· ≥ λn−1(G)≥λn(H) = λn(G)=0.

Let Ais a symmetric real matrix whose rows and columns are indexed by X=

{1,2, . . . , n}.Let {X1, X2, . . . , Xn}be a partition of X. The characteristic matrix S

is the n×mwhose j−th column is the characteristic vector of Xj(j= 1, . . . , m).

Deﬁne ni=|Xi|and the diagonal matrix K=diag(n1, . . . , nm).Let Abe partitioned

according to {X1, X2, . . . , Xn}, that is

A=





A11 ··· A1m

.....

Am1··· Amm







where Aij denotes the submatrix (block) of Aformed by rows in Xiand the column in

Xj.Let bij the average row sum of Aij .Then the matrix B= (bij ) is called the quotient

matrix. We easily have KB =STAS and STS=K. If the row sum of each block Aij is

constant the partition is called equitable. If each vertex in Xihas the same number bij

of neighbors in part Xj,for any j(or any j6=i), the partition is called almost equitable.

Lemma 5 ([3]) Let Abe a symmetric matrix of order n, and suppose Pis a partition of

{1, . . . , n}such that the corresponding partition of Ais equitable with quotient matrix B.

Then the spectrum of Bis a sub(multi)set of the spectrum of A, and all corresponding

eigenvectors of Aare in the column space of the characteristic matrix Cof P(this

means that the entries of the eigenvector are constant on each partition class Ui). The

remaining eigenvectors of Aare orthogonal to the columns of Cand the corresponding

eigenvalues remain unchanged if the blocks Ai,j are replaced by Ai,j +ci,j Jfor certain

constants ci,j (as usual, Jis the all-one matrix).

We will denote by Kn,Snand Kn1,n2the complete graph, star graph and complete

bipartite graph, respectively such that n1≥n2and n=n1+n2.

3 Bounds on the sum of the two largest eigenvalues

Our main result of this section is a sharp lower bound on the sum of the two largest

signless Laplacian (Theorem 12). Some preparation is required. To obtain the main

result we ﬁrst prove some auxiliary results for a subgraph Hof Gby considering the

two vertices of the largest degrees and their neighbors.

Let uand vbe the vertices with the two largest degrees of a graph G, that is,

|N(u)|=d1(G) and |N(v)|=d2(G). A subgraph H(VH, EH) of Gcan be obtained by

taking the vertex set as VH={vi∈V|vi∈N(u)∪N(v)∪{u}∪{v}} and the edge set

as EH={(vi, vj)∈E|vi∈ {u, v}and vj∈N(u)∪N(v)}.

We improve the lower bound from [4], q1(G)≥d1(G) + 1. Roughly speaking, the

proofs of our main results in this section (Theorems 12 and 14) follow from the fact that

q1(G) + q2(G)≥q1(H) + q2(H) (by Theorems 2,3,4) and also that d1(G) + d2(G) =

d1(H) + d2(H) since we did not remove any vertex from N(u) and N(v) of Gto build

the graph H. In fact, if we prove that q1(H) + q2(H)≥d1(H) + d2(H) + 1, we are done.

Before proving that, we need to introduce some notation, several preliminary results

and two types of graphs obtained by the deﬁnition of H= (VH, EH).

Let S1=N(u)\(N(v)∪v), S2=N(u)∩N(v) and S3=N(v)\(N(u)∪u), such

that |S1|=r,|S2|=pand |S3|=s. Figure 1 displays the two possible types of graphs

isomorphic to H. Notice that if uand vare not adjacent, Hbelongs to H(p, r, s) such

that d1(G) = d1(H) = p+rand d2(G) = d2(H) = p+s. If uand vare adjacent, H

belongs to G(p, r, s) such that d1(G) = d1(H) = p+r+1 and d2(G) = d2(H) = p+s+1.

Figure 1: Families of graphs of the type H(VH, EH).

Lemmas 6and 7establish lower bounds to q1(G) and q2(G) in terms of d1(G) and

d2(G) that will be useful for our purposes here.

Lemma 6 ([4]) Let Gbe a connected graph on n≥4vertices. Then,

q1(G)≥d1(G)+1

with equality if and only if Gis the star Sn.

Lemma 7 ([9]) Let Gbe a graph. Then

q2(G)≥d2(G)−1.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

BoundingthesumofthelargestsignlessLaplacianeigenvaluesofagraphAidaAbiad*LeonardodeLima§SinaKalantarzadeh¶MonaMohammadiCarlaOliveira**AbstractWeshowseveralsharpupperandlowerboundsforthesumofthelargesteigenvaluesofthesignlessLaplacianmatrix.Theseboundsimproveandextendpreviouslyknownbounds.AMSclassi...

展开>> 收起<<

Bounding the sum of the largest signless Laplacian eigenvalues of a graph Aida AbiadLeonardo de LimaSina Kalantarzadeh.pdf

共16页,预览4页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Bounding the sum of the largest signless Laplacian eigenvalues of a graph Aida AbiadLeonardo de LimaSina Kalantarzadeh

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: