# The Distance Laplacian Spectral Radius of Clique Trees

Authors: Xiaoling Zhang; Jiajia Zhou
Journal: Discrete Dynamics in Nature and Society
 (2020)

---

## Abstract

The distance Laplacian matrix of a connected graphG is defined as ℒG=TrG−DG, where DG is the distance matrix of G and TrG is the diagonal matrix of vertex transmissions of G. The largest eigenvalue of ℒG is called the distance Laplacian spectral radius of G. In this paper, we determine the graphs with maximum and minimum distance Laplacian spectral radius among all clique trees with n vertices and k cliques. Moreover, we obtainn vertices and k cliques.


---

## Body

## 1. Introduction

In this paper, we consider simple connected graphs [1]. A graph G is represented by G=VG,EG, in which the set VG=v1,v2,…,vn represents its vertex set and EG is the edge set connecting pairs of distinct vertices. The number n=VG is referred to as the order of G. The distance matrix of G is the n×n matrix DG=dGu,vu,v∈VG, where dGu,v denotes the distance between vertices u and v in G, i.e., the length of a shortest path from u to v in G. For u∈VG, the transmission of u in G, denoted by TrGu, is defined as the sum of distances from u to all other vertices of G. Let TrG be the diagonal matrix of vertex transmissions of G. In 2013, Aouchiche and Hansen [2] first gave the definition of distance Laplacian matrix: for a connected graph G, ℒG=TrG−DG, where ℒG denotes the distance Laplacian matrix. Obviously, ℒG is a positive semidefinite, symmetric, and singular matrix. The distance Laplacian eigenvalues of G, denoted by λ1G≥λ2G≥⋅⋅⋅≥λnG=0, are the eigenvalues of ℒG. Especially, the largest eigenvalue λ1G is the distance Laplacian spectral radius of G. The positive unit eigenvector, i.e., all components of the eigenvector are positive, corresponding to λ1G is called the Perron eigenvector of ℒG.For a graphG, two vertices are called adjacent if they are connected by an edge and two edges are called incident if they share a common vertex. The set of vertices that are adjacent to a vertex v∈VG is called the neighborhood of v and is presented by NGv. As usual, let Kn, K1,n−1, and Pn denote the complete graph, the star, and the path with order n, respectively. G is a connected graph, X∈VG, G−X is not connected, and then X is a cut-vertex set. If X has only vertex v, then v is a cut-vertex. A block of G is a maximal connected subgraph of G that has no cut-vertex. A block is a clique if the block is a complete graph. A graph G is a clique tree if each block of G is a clique. We call Pn1,n2,…,nk a clique path if we replace each edge of Pk+1 by a clique Kni such that VKni∩VKni+1=vi for i=1,2,…,k−2 and VKni∩VKnj=∅ for j≠i−1,i+1 and 2≤i≤k−1. We call Ku,n1,n2,…,nk a clique star if we replace each edge of the star K1,k with a clique Kni such that VKni∩VKnj=u for i≠j and i,j=1,2,…,k (see Figure 1).Figure 1
A clique star and a clique path.Recently, Xing and Zhou [3] characterized the unique graph with minimum distance Laplacian spectral radius among all the bicyclic graphs with fixed number of vertices; Aouchiche and Hansen [4] showed that the star K1,n is the unique tree with the minimum distance Laplacian spectral radius among all trees; Lin et al. [5, 6] determined the unique graph with minimum distance Laplacian spectral radius among all the trees with fixed bipartition, nonstar-like trees, noncaterpillar trees, nonstar-like noncaterpillar trees, and the graph with fixed edge connectivity at most half of the order, respectively; Niu et al. [7] determined the unique graph with minimum distance Laplacian spectral radius among all the bipartite graphs with fixed matching number and fixed vertex connectivity, respectively; Fan et al. [8] determined the graph with minimum distance Laplacian spectral radius among all the unicyclic and bicyclic graphs with fixed numbers of vertices, respectively; Lin and Zhou [9] determined the unique graph with maximum distance Laplacian spectral radius among all the unicyclic graphs with fixed numbers of vertices.In 2019, Cui et al. [10] investigated a convex combination of TrG and DG in the form of DαG=αTrG+1−αDG, 0≤α≤1, which is called the generalized distance matrix. Alhevaz et al. [11] gave some new upper and lower bounds for the generalized distance energy of graphs which are established based on parameters including the Wiener index and the transmission degrees and found that the complete graph has the minimum generalized distance energy among all connected graphs; Lin and Drury et al. [12] established some bounds for the generalized distance Gaussian Estrada index of a connected graph, involving the different graph parameters, including the order, the Wiener index, the transmission degrees, and the parameter α∈0,1, and characterized the extremal graphs attaining these bounds; Alhevaz et al. [13] obtained some bounds for the generalized distance spectral radius of graphs using graph parameters like the diameter, the order, the minimum degree, the second minimum degree, the transmission degree, and the second transmission degree and characterized the extremal graphs; Alhevaz et al. [14] studied the generalized distance spectrum of join of two regular graphs and join of a regular graph with the union of two different regular graphs; Shang [15] established better lower and upper bounds to the distance Estrada index for almost all graphs.The distance Laplacian energy is defined asDLEG=1/n∑i=1nλiG−tG, where tG is the average transmission of G and is defined by tG=1/n∑i=1nTrGvi. Although there has been extensive work done on the distance Laplacian spectral radius of graphs, relatively little is known in regard to distance Laplacian energy. The distance Laplacian energy was first introduced in [16], where several lower and upper bounds were obtained; Das et al. [17] gave some lower bounds on distance Laplacian energy in terms of n for graphs and trees and characterized the extremal graphs and trees. In this paper, first, we not only get the distance Laplacian eigenvalues of all clique stars Ku,n1,n2,…,nk but also get their distance Laplacian energies; second, we prove all clique stars Ku,n1,n2,…,nk are the graphs with minimum distance Laplacian spectral radius among all clique trees with n vertices and k cliques. Then, we show that the clique path Pm,2,…,2,n−m−k+3 for m≥3 is the graph with maximum distance Laplacian spectral radius among all clique trees with n vertices and k cliques.


## 2. Preliminaries

LetG=V,E be a connected graph with VG=v1,v2,…,vn. A column vector x=xv1,xv2,…,xvnT∈ℝn can be considered as a function defined on VG which maps vertex vi to xvi, i.e., xvi=xvi for i=1,2,…,n. Then,(1)xTℒGx=∑u,v⊆VGdGu,vxu−xv2,and λ is a distance Laplacian eigenvalue with corresponding eigenvector x if and only if x≠0, for each u∈VG,(2)λ−TrGuxu=−∑v∈VGdGu,vxv,or equivalently(3)λxu=∑v∈VGdGu,vxu−xv.The above equation is called the eigenequation ofG at u.Note that1n=1,1,…,1︸nT is an eigenvector of ℒG corresponding to λnG=0. For n≥2, if x is an eigenvector of ℒG corresponding to λ1G, we have xT1n=0.For a unit column vectorx∈ℝn, by Rayleigh’s principle, we have λG≥xTℒGx with equality if and only if x is an eigenvector of ℒG corresponding to λG.The following is the well-known Cauchy interlacing theorem.Lemma 1 (Cauchy interlace theorem) (see [1]).
LetA be a Hermitian matrix with eigenvalues λ1≥⋯≥λn and B be one of its principal submatrices. Let B have eigenvalues μ1≥⋯≥μm. Then, the inequalities λn−m+i≤μi≤λii=1,…,m hold.Lemma 2 (see [6]).
LetG be a connected graph with three induced subgraphs G1, G2, and G3 such that VGi≥2 for i=1,2,3 and VGi∩VGj=u for 1≤i<j≤3 and ∪i=13VGi=VG (see Figure 2). For v∈VG2\u and y∈VG1\u, let G1=G−uω:ω∈NG3u+vω:ω∈NG3u and G2=G−uω:ω∈NG3u+yω:ω∈NG3u. If NGu=y,v∪NG3u, then λ1G<λ1G1 or λ1G<λ1G2.Figure 2
A graph transformation fromG to G1 and G2.


## 3. Minimum Distance Laplacian Spectral Radius of Clique Trees

The diameter of a graph is the maximum distance between any pair of vertices.Lemma 3.
LetS be a clique tree with n vertices and k cliques. If diamS≥3, then λ1S>2n−1.Proof.
For convenience, letdiamS=d and Pn1,n2,…,nd be a clique path of S. Denote the cliques of Pn1,n2,…,nd by Kn1, Kn2,…,Knd. Let VKni∩VKni+1=vi for i=1,2,…,d−1. Let v0∈VKn1\v1 and vd∈VKnd\vd−1. Then, v0v1…vd is a diameter path of S. We can easily get(4)TrSv0≥n1−2+2n2−2+⋯+dnd−2+1+2+⋯+d+2n−n1−n2−⋅⋅⋅−nd+d−1,TrSvd≥nd−2+2nd−1−2+⋯+dn1−2+1+2+⋯+d+2n−n1−n2−⋯−nd+d−1.
Then, we have(5)TrSv0+TrSvd≥d+1n1−2+n2−2+⋯+nd−2+dd+1+4n−4n1−2+n2−2+⋯+nd−2−8d+4d−1=d+1−4n1−2+n2−2+⋯+nd−2+dd+1+4n−8d+4d−1=d−3n1−2+n2−2+⋯+nd−2+d2+4n−3d−4>4n+d2−3d−8.
LetM be the principal submatrix of ℒS indexed by v0 and vd. Then,(6)M=TrSv0−d−dTrSvd,M−λE==TrSv0−λ−d−dTrSvd−λ=λ2−TrSv0+TrSvdλ+TrSv0TrSvd−d2,and thus (7)λ1M=TrSv0+TrSvd+TrSv0−TrSvd2+4d22≥TrSv0+TrSvd+2d2>4n+d2−d−82≥4n+32−3−82=2n−1.
By Lemma2, we have λ1S≥λ1M>2n−1.Theorem 1.
LetKu,n1,n2,…,nk be an arbitrary clique star with n vertices and k cliques. Then, λ1Ku,n1,n2,…,nk=2n−1.Proof.
Obviously, we haven1+n2+n3+⋅⋅⋅+nk=n+k−1. Let x be a Perron eigenvector of ℒKu,n1,n2,…,nk corresponding to λ1Ku,n1,n2,…,nk. By symmetry, we may assume xv=xi for any v∈VKni∖u, i=1,2,…,k. Let x0=xu, then we have (8)λx0=n1−1x0−x1+n2−1x0−x2+n3−1x0−x3+⋯+nk−1x0−xk,λx1=x1−x0+2n2−1x1−x2+2n3−1x1−x3+⋯+2nk−1x1−xk,λx2=x2−x0+2n1−1x2−x1+2n3−1x2−x3+⋯+2nk−1x2−xk,λx3=x3−x0+2n1−1x3−x1+2n2−1x3−x2+⋯+2nk−1x3−xk,…λxk=xk−x0+2n1−1xk−x1+2n2−1xk−x2+⋯+2nk−1−1xk−xk−1.
Thus,λ1 is the largest root of the equation fn1,n2,…,nkt=0, where β=∑i=1kni−k and (9)fn1,n2,…,nkt=β−t1−n11−n2⋯1−nk−12β−n1+3−t2−2n2⋯2−2nk−12−2n12β−n2+3−t⋯2−2nk⋮⋮⋮⋱⋮−12−2n12−2n2⋯2β−nk+3−t=−t1−n11−n2⋯1−nk−t2β−n1+3−t2−2n2⋯2−2nk−t2−2n12β−n2+3−t⋯2−2nk⋮⋮⋮⋱⋮−t2−2n12−2n2⋯2β−nk+3−t=−t1−n11−n21−n3⋯1−nk−t2β−n1+3−t2−2n22−2n3⋯2−2nk01−2n+t2n−1−t0⋯0⋮⋮⋮⋮⋱⋮01−2n+t00⋯2n−1−t=−t1−n−t1−n21−n3⋯1−nk−t1−2t2−2n22−2n3⋯2−2nk002n−1−t0⋯0⋮⋮⋮⋮⋱⋮0000⋯2n−1−t=−t−122n−1−tk−11−2t+−t−132n−1−tk−11−n−t=2n−1−tk−11−2t−t+1−n−tt=t2n−1−tk−1t−n.
Therefore, we haveλ1Ku,n1,n2,…,nk=2n−1 n and 0 are also distance Laplacian eigenvalues of Ku,n1,……,ukK…….
Combining Lemma3 and Theorem 1, we have the following result.Theorem 2.
Among all clique trees withn vertices and k cliques, the graphs attaining the minimum distance Laplacian spectral radius are clique stars Ku,n1,n2,…,nk.LetI be the identity matrix of order n. The characteristic polynomial of ℒG can be written as ψG:λ=detλI−ℒG. Let us label the vertices of Ku,n1,n2,…,nk such that u is the first vertices, and the first n1 vertices are from VKn1, the following n2−1 vertices are from VKn2\u, …, and the last nk−1 are from VKnk\u. Let detλI−ℒKu,n1,n2,…,nk=0. Combining Theorem 1, by direct calculations, we get the following result.Corollary 1.
The distance Laplacian eigenvalues ofKu,n1,n2,…,nk are 2n−1 of multiplicities k−1, 2n−ni of multiplicities ni−21≤i≤k, n, and 0.Theorem 3.
LetKu,n1,n2,…,nk be an arbitrary clique star with n vertices and k cliques. Then, we have DLEKu,n1,n2,…,nk=2/n2n−1+1/nk−1−∑i=1kni2.Proof.
Obviously, we haven1+n2+n3+⋅⋅⋅+nk=n+k−1. For convenience, let G=Ku,n1,n2,…,nk. For any v,w∈VKni\u, we have TrGv=TrGw. Let vi∈VKni\u, 1≤i≤k. Then, we have TrGvi=2n−ni−1 and tG=1/n∑i=1nTrGvi=∑i=1kni−12n−ni−1+n−1/n=2n∑i=1kni−1−∑i=1kni−1ni+1+n−1/n=2nn−1−∑i=1kni2+k+n−1/n=2n−1+k−1−∑i=1kni2/n. By Cauchy–Schwarz inequality, we have ∑i=1kni2≥n+k−12>n2. So, we get tG<2n−1+k−1−n2/n=n−1+k−1/n<n. By Corollary 1, we know λi>n>tG for i=1,2,…,n−1, and λn=0. DLEKu,n1,n2,…,nk=1/n∑i=1nλiG−tG=∑i=1n−1λiG−tG+tG/n=∑i=1nλiG+2−ntG/n=2tG/n since ∑i=1nλiG is equal to the trail of ℒG, i.e., ∑i=1nλiG=∑i=1nTrGvi. So, we get DLEKu,n1,n2,…,nk=2/n2n−1+1/nk−1−∑i=1kni2.


## 4. Maximum Distance Laplacian Spectral Radius of Clique Trees

Lemma 4.
LetH be a connected graph and S be a clique tree with diamS=d. Suppose Pn1,n2,…,nd is a clique path of S with cliques Kn1, Kn2,…, Knd and VKni∩VKni+1=vi for i=1,2,…,d−1. Let Ht be the graph obtained by identifying a vertex v of H and a vertex u of Knt, where 2≤t≤d−1. Then, λ1Hd>λ1Ht or λ1H1>λ1Ht.Proof.
By Lemma2, we may assume u≠vt−1 or u≠vt for 2≤t≤d−1. Denote the component of S−vt−1 which contains vertex vt−2 by S1 and the component of S−vt which contains vertex vt+1 by S2. Let S1=VS1, S2=VS2, and S3=VS\VS1∪VS2. Suppose x is a Perron eigenvector of ℒHt corresponding to λ1Ht. In the following, we will first prove λ1Ht+1>λ1Ht or λ1Ht−1>λ1Ht.Case 1:∑h∈VH\v∑ω∈S1xω−xh2≥∑h∈VH\v∑ω∈S2xω−xh2. From Ht to Ht+1, we have(10)dHtω,h−dHt+1ω,h=−1,ω∈S1∪S3\vt,h∈VH\v,1,ω∈S2,h∈VH\v,0,otherwise,λ1Ht+1−λ1Ht≥xTℒHt+1−ℒHtx=∑h∈VH\v∑ω∈S1∪S3\vtxω−xh2−∑ω∈S2xω−xh2=∑h∈VH\v∑ω∈S1xω−xh2+∑ω∈S3\vtxω−xh2−∑ω∈S2xω−xh2≥∑h∈VH\v∑ω∈S1xω−xh2−∑ω∈S2xω−xh2≥0.Thus,λ1Ht+1≥λ1Ht.In the following, we will proveλ1Ht+1>λ1Ht. If λ1Ht+1=λ1Ht, then ∑h∈VH\v∑ω∈S3\vtxω−xh2=0, which implies xω=xh for any ω∈S3\vt, h∈VH\v, and x is also a Perron eigenvector of ℒHt+1 corresponding to λ1Ht+1. For arbitrary ω1∈S1, from the eigenequations of Ht+1 and Ht at ω1, we have(11)λ1Ht+1xω1=∑h∈VHt+1dHt+1ω1,hxω1−xh=∑h∈VHtdHtω1,hxω1−xh+∑h∈VH\vxω1−xh=λ1Htxω1+∑h∈VH\vxω1−xh.So, we have∑h∈VH\vxω1−xh=0. Similarly, for arbitrary ω2∈S2 and ω3∈S3\vt, we have ∑h∈VH\vxω2−xh=0 and ∑h∈VH\vxω3−xh=0. Then, we have xω=xw for any ω,w∈VHt\vt. Since xT1VHt=0, we have VHt−1xv1+xvt=0, which implies xv1≠0 and xvt≠0.From the eigenequation ofHt at v1 and v2, we have 0=λ1Htxv1−λ1Htxv2=∑h∈VH\vxv1−xh+xvt=xvt, which is a contradiction.Up to now, we have provedλ1Ht+1>λ1Ht.Case 2:∑h∈VH\v∑ω∈S1xω−xh2<∑h∈VH\v∑ω∈S2xω−xh2.
FromHt to Ht−1, we have (12)dHtω,h−dHt−1ω,h=−1,ω∈S2∪S3\vt−1,h∈VH\v,1,ω∈S1,h∈VH\v,0,otherwise.
Then, we have(13)λ1Ht−1−λ1Ht≥xTℒHt−1−ℒHtx=∑h∈VH\v∑ω∈S2xω−xh2+∑ω∈S3\vt−1xω−xh2−∑ω∈S1xω−xh2≥∑h∈VH\v∑ω∈S2xω−xh2−∑ω∈S1xω−xh2>0.
Thus,λ1Ht−1>λ1Ht.
In the following, we will proveλ1Hd>λ1Ht or λ1H1>λ1Ht.
Ifλ1Ht+1>λ1Ht, we may denote the component of S−vt which contains vertex vt−1 by S1′ and the component of S−vt+1 which contains vertex vt+2 by S2′. Let S1′=VS1′, S2′=VS2′, and S3′=VS\VS1′∪VS2′. Let x′ be a Perron eigenvector of ℒHt+1 corresponding to λ1Ht+1. If ∑h∈VH\v∑ω∈S1′xω′−xh′2<∑h∈VH\v∑ω∈S2′xω′−xh′2, then λ1Ht−λ1Ht+1≥∑h∈VH\v∑ω∈S2′xω′−xh′2−∑ω∈S1′xω′−xh′2, and we can get λ1Ht>λ1Ht+1, which is a contradiction. So, we have ∑h∈VH\v∑ω∈S1′xω′−xh′2≥∑h∈VH\v∑ω∈S2′xω′−xh′2. Then, we have λ1Ht+2−λ1Ht+1≥∑h∈VH\v∑ω∈S1′xω′−xh′2−∑ω∈S2′xω′−xh′2≥0, similar to case 1, and we can get the equal sign in the above inequality does not hold. So, we have λ1Ht+2>λ1Ht+1. Repeating the above procedure, we can get λ1Hd>⋯>λ1Ht+2>λ1Ht+1>λ1Ht.
Similarly, ifλ1Ht−1>λ1Ht, we can prove λ1H1>⋯>λ1Ht−2>λ1Ht−1>λ1Ht.Theorem 4.
Among all clique trees withn vertices and k cliques, the graph attaining the maximum distance Laplacian spectral radius is Pm,2,…,2,n−m−k+3 for some m≥3.Proof.
LetG be the graph with maximum distance Laplacian spectral radius among all clique trees with n vertices and k cliques. By Lemma 4, we get G=Pn1,n2,…,nk. Let VKni∩VKni+1=vi for i=1,2,…,k−1. If k≤2, the result holds. Next, we may assume k≥3. Suppose there exists some 2≤t≤k such that nt≥3. Denote the component of G−vt−1 which contains vertex vt−2 by G1 and the component of G−vt which contains vertex vt+1 by G2. Let S1=VG1, S2=VG2, and S3=VG\VG1∪VG2, i.e., S3=VKnt. Let (14)Gt−1=G−vvt|v∈VKnt\vt−1,vt+uv|u∈VKnt−1\vt−1,v∈VKnt\vt−1,vt,Gt+1=G−vt−1|v∈VKnt\vt−1,vt+uv|u∈VKnt−1\vt,v∈VKnt\vt−1,vt,i.e., Gt−1=Pn1,…,nt−2,nt−1+nt−2,2,nt+1,…,nk and Gt+1=Pn1,…,nt−1,2,nt+1+nt−2,nt+2,…,nk. Suppose x is a Perron eigenvector of ℒG corresponding to λ1G. In the following, we will first prove λ1Gt−1>λ1G or λ1Gt+1>λ1G.Case 1:∑ω∈S2∑h∈S3\vt−1,vtxω−xh2≥∑ω∈S1∑h∈S3\vt−1,vtxω−xh2.FromG to Gt−1, we have(15)dGω,h−dGt−1ω,h=−1,ω∈S2∪vt,h∈S3\vt−1,vt,1,ω∈S1,h∈S3\vt−1,vt,0,otherwise.λ1Gt−1−λ1G≥xTℒGt−1−ℒGx=∑h∈S3\vt−1,vt∑ω∈S2∪vtxω−xh2−∑ω∈S1xω−xh2=∑h∈S3\vt−1,vt∑ω∈S2xω−xh2+xvt−xh2−∑ω∈S1xω−xh2≥∑h∈S3\vt−1,vt∑ω∈S2xω−xh2−∑ω∈S1xω−xh2≥0,which impliesλ1Gt−1≥λ1G. Similar to Case 1 of Lemma 4, we can get the equal sign in the above inequality does not hold. So, we have λ1Gt−1≥λ1G.Case 2:∑ω∈S2∑h∈S3\vt−1,vtxω−xh2<∑ω∈S1∑h∈S3\vt−1,vtxω−xh2.Then, we have(16)λ1Gt+1−λ1G≥xTℒGt+1−ℒGx=∑h∈S3\vt−1,vt∑ω∈S1∪vt−1xω−xh2−∑ω∈S2xω−xh2=∑h∈S3\vt−1,vt∑ω∈S1xω−xh2+xvt−1−xh2−∑ω∈S2xω−xh2≥∑h∈S3\vt−1,vt∑ω∈S1xω−xh2−∑ω∈S2xω−xh2>0.Thus, we haveλ1Gt+1>λ1G.
Doing the above graph transformations untiln2=n3=⋯=nk−1=2, we get G as Pm,2,…,2,n−m−k+3 for some m≥3.


## 5. Conclusion

This paper mainly determines the extremal graphs with maximum and minimum distance Laplacian spectral radius among all clique trees withn vertices and k cliques. Moreover, we get the distance Laplacian energies of all the clique stars with n vertices and k cliques. Based on our results, we conjecture that the line graphs of Sn+ and Kin,3 are the unique graphs with minimum and maximum distance Laplacian spectral radius among all the line graphs of unicyclic graphs, respectively, where Sn+ is the graph obtained by adding an edge to the star K1,n−1 of order n and Kin,3 is the graph obtained by adding an edge between a vertex of a triangle and a terminal vertex of a path on n−3 vertices. Moreover, we can study the distance Laplacian spectral radius of diclique trees in the future.



---

*Source: 8855987-2020-12-09.xml*