Distribution of signless Laplacian eigenvalues and degree sequence

S. Akbari, M. Darougheh, L. S. de Lima, D. Traciná · 2026

Read Distribution of signless Laplacian eigenvalues and degree sequence by S. Akbari, M. Darougheh, L. S. de Lima, D. Traciná (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-27405.txt.

Introduction

Saieed Akbari and colleagues characterize signless Laplacian eigenvalues of graphs through their degree sequences. They pin down all graphs meeting a set of eigenvalue-count conditions on intervals set by the smallest and largest degrees. They also show no graph meets one count condition, classify the disconnected cases for another, and pose two open problems.

Catalog record

CREATORS. Akbari, M. Darougheh, L. S. de Lima, D. Traciná
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE30739
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.27405

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Distribution of signless Laplacian eigenvalues and degree sequence S. Akbari, M. Darougheh, L. S. de Lima, D. Traciná Abstract Let G G be a graph of order n n with degree sequence d 1 ≥ ⋯ ≥ d n d_{1}\geq\cdots\geq d_{n} . Let m G ​ ​ I m_{G}\emph{I} be the number of signless Laplacian eigenvalues in an interval ​ I . \emph{I}. In this paper, we characterize the distribution of the signless Laplacian eigenvalues in terms of the degree sequence of a graph within specific subintervals of [ 0 , 2 ​ n − 2 ] . [0,\,2n-2]. We determine all graphs G G such that m G ​ [ d n , 2 ​ n − 2 ] ≤ 2 , m G ​ [ d n − 1 , 2 ​ n − 2 ] = 1 , m G ​ [ 0 , d 1 ] ≤ 2 . m_{G}[d_{n},2n-2]\leq 2,\;m_{G}[d_{n-1},2n-2]=1,\;m_{G}[0,d_{1}]\leq 2. We also prove that there is no graph such that m G ​ [ 0 , d 3 ] = 1 m_{G}[0,d_{3}]=1 . In addition, we obtain all disconnected graphs such that m G ​ [ 0 , d 1 ] = 3 m_{G}[0,d_{1}]=3 . Finally, we propose two open problems for future research. 2020 MSC 05C07 , 05C50 , 15A18 1 Introduction Let G be a simple graph of order n , with the vertex set V(G) and edge set E(G) . The degree sequence of G is denoted by d_{1}\geq\cdots\geq d_{n} . We write A(G) for the adjacency matrix of G , and D(G) for the diagonal matrix of vertex degrees. The matrix Q(G)=A(G)+D(G) is called the signless Laplacian of G , and its eigenvalues are denoted by q_{1}(G)\geq\cdots\geq q_{n}(G) . It is well known that the signless Laplacian matrix Q(G) is positive semidefinite, so all its eigenvalues are non-negative. Furthermore, Gershgorin’s circle theorem implies that q_{1}(G)\leq 2n-2 . Thus the signless Laplacian spectrum of any graph of order n is contained in the interval [0,\,2n-2] . An extensive body of research has investigated how Laplacian eigenvalues are distributed within prescribed intervals; see, for example, [ 1 , 2 , 3 , 5 , 10 , 11 , 18 , 19 ] . These works establish connections between the placement of Laplacian eigenvalues and various structural characteristics of the underlying graph, including the domination number, independence number, vertex connectivity, diameter, and degree sequence. Recently, similar works have focused on the distribution of the eigenvalues of the signless Laplacian matrix within a given subinterval of [0,\,2n-2] ; see, for instance, [ 20 , 9 , 17 , 14 ] . For convenience, we denote by m_{G}I , where I\subseteq[0,\,2n-2] , the number of signless Laplacian eigenvalues of a graph G of order n that lie in I (counted with multiplicities). In this paper, we address the distribution of the signless Laplacian eigenvalues in terms of the degree sequence of a graph within specific subintervals of [0,\,2n-2]. The paper is organized as follows. In Section 2, we state several known results from the literature that will be used in our proofs. In Section 3, we characterize all graphs satisfying m_{G}[d_{n},\,2n-2]\leq 2 , m_{G}[d_{n-1},\,2n-2]=1 , and m_{G}[0,\,d_{1}]\leq 2 . For disconnected graphs, we also determine all graphs for which m_{G}[0,\,d_{1}]=3 . In addition, we prove that there is no graph G such that m_{G}[0,\,d_{3}]=1 , along with several related auxiliary results. Section 4 contains our concluding remarks, in which we propose two problems. 2 Preliminaries In this section, we introduce the notation and basic concepts used throughout the paper. For a graph G and a vertex v\in V(G) , the open neighborhood of v is N_{G}(v)=\{u\in V(G):uv\in E(G)\} , and the closed neighborhood of v is N_{G}[v]=N_{G}(v)\cup\{v\} . The degree of v is d_{G}(v)=|N_{G}(v)| . A set S\subseteq V(G) is independent if no two vertices of S are adjacent. The independence number of G is \alpha(G)=\max\{|S|:S\subseteq V(G)\ \text{is independent}\} . We denote by P_{n} , C_{n} , S_{n} , and K_{n} the path, cycle, star, and complete graph of order n , respectively. For a partition n_{1},\dots,n_{k} of n , we write K_{n_{1},\dots,n_{k}} for the complete k -partite graph with part sizes n_{1},\dots,n_{k} . Given two graphs G and H , their disjoint union is denoted by G\cup H . If G is a graph and k\geq 1 , the notation kG stands for the disjoint union of k copies of G . The join of G and H , denoted by G\vee H , is obtained from G\cup H by adding all edges between V(G) and V(H) . For an n\times n real symmetric matrix M , we write \operatorname{Spec}(M) for the multiset of its eigenvalues. We denote the multiplicity of an eigenvalue \lambda of M by {\lambda^{\left[{{m}}\right]}} , where m is the multiplicity of \lambda . In particular, the signless Laplacian spectrum of G is \operatorname{Spec}(G)=\operatorname{Spec}(Q(G)) and the eigenvalues of A(G) will be denoted by \lambda_{1}(G)\geq\cdots\geq\lambda_{n}(G) . Lemma 2.1 ( [ 7 ] , Theorem 1.3.15) . Let A and B be n\times n Hermitian matrices. Suppose that \lambda_{1}(A)\geq\cdots\geq\lambda_{n}(A) and \lambda_{1}(B)\geq\cdots\geq\lambda_{n}(B) are eigenvalues of A and B , respectively. Then \lambda_{i}(A+B)\leq\lambda_{j}(A)+\lambda_{i-j+1}(B)\quad(1\leq j\leq i\leq n), \lambda_{i}(A+B)\geq\lambda_{j}(A)+\lambda_{i-j+n}(B)\quad(1\leq i\leq j\leq n). Lemma 2.2 ( [ 12 ] , Theorem 4.3.28) . If M is a Hermitian matrix of order n and B is its principal submatrix of order p , then \lambda_{n-p+i}(M)\leq\lambda_{i}(B)\leq\lambda_{i}(M) for 1\leq i\leq p . The following fact is an immediate consequence of Weyl’s inequalities (Lemma 2.1 ) and Cauchy’s interlacing theorem. We therefore omit the proof. Corollary 2.3 . Let G be a graph of order n , and let H be an induced subgraph of G . Then, for every a\in[0,\,2n-2] , m_{H}[a,\,2n-2]\;\leq\;m_{G}[a,\,2n-2]. Given a graph G and a set of edges S\subseteq E(G) , we denote by G-S the subgraph obtained from G by deleting all edges in S . In particular, when S=\{e\} for some edge e , we simply write G-e . Conversely, if a graph G^{\prime} satisfies G^{\prime}=G-S for some S\subseteq E(G) , then we may recover G from G^{\prime} by adding back the edges of S ; in this case we write G=G^{\prime}+S . Lemma 2.4 ( [ 6 ] , Theorem 2.1) . Let G be a graph with n vertices and let e\in E(G) . Then q_{1}(G)\geq q_{1}(G-e)\geq q_{2}(G)\geq\dots\geq q_{n}(G)\geq q_{n}(G-e). Lemma 2.5 ( [ 12 ] , Corollary 4.3.5) . Let A and B be real symmetric n\times n matrices. Suppose \operatorname{rank}(B)=r . Then the inertia of A+B is controlled by that of A in the following way: \displaystyle n_{+}\!\left(A\right)-r\;\leq\;n_{+}\!\left(A+B\right)\;\leq\;n_{+}\!\left(A\right)+r, \displaystyle n_{-}\!\left(A\right)-r\;\leq\;n_{-}\!\left(A+B\right)\;\leq\;n_{-}\!\left(A\right)+r, \displaystyle n_{0}\!\left(A\right)-r\;\leq\;n_{0}\!\left(A+B\right)\;\leq\;n_{0}\!\left(A\right)+r, where for any symmetric matrix X,\,n_{+}\!\left(X\right),n_{-}\!\left(X\right)\text{ and }n_{0}\!\left(X\right) denote respectively the numbers of positive, negative and zero eigenvalues of X , counted with algebraic multiplicity. Lemma 2.6 ( [ 20 ] , Theorem 3.2) . For a graph G with n vertices, \alpha(G)\leq\min\{m_{G}[d_{n},\,2n-2],m_{G}[0,\,d_{1}]\} . Definition 2.7 ( [ 15 ] , Definition 2.12) . For every integer n\geq 2 , let G_{n} be the graph of order n obtained from the disjoint union of complete graphs K_{\lceil n/2\rceil} and K_{\lfloor n/2\rfloor} as follows. Let V(K_{\lceil n/2\rceil})=\{v_{1},\dots,v_{\lceil n/2\rceil}\} and V(K_{\lfloor n/2\rfloor})=\{w_{1},\dots,w_{\lfloor n/2\rfloor}\} . We then add edges between vertices of K_{\lceil

Read the complete text