# On the Change of Distance Energy of Complete Bipartite Graph due to Edge Deletion

Authors: Shaowei Sun; Ziyan Wan
Journal: Journal of Mathematics
 (2021)

---

## Abstract

The distance energy of a graph is defined as the sum of absolute values of distance eigenvalues of the graph. The distance energy of a graph plays an important role in many fields. By constructing a new polynomial, we transform a problem on the sum of the absolute values of the roots of a quadratic polynomial into a problem on the largest root of a cubic polynomial. Hence, we give a new and shorter proof on the change of distance energy of a complete bipartite graph due to edge deletion, which was given by Varghese et al.


---

## Body

## 1. Introduction

LetG=VG,EG be a simple connected graph, whose vertex set is VG=v1,v2,…,vn and edge set is EG. For any pair of vertices (vi,vj), the distance dvi,vj is defined as the length of the shortest path between vi and vj. In particular, dvi,vi=0 for any vi∈VG. The distance matrix of G, denoted by DG, is the n×n matrix with i,j-entry being dvi,vj. The distance energy EDG of G is defined by the sum of absolute values of distance eigenvalues of G. The distance energy of G has been studied for several years in the literature, see [1–5] and the references therein.It is not easy to compute the distance energy of general graphs. Thus, we are interested in finding the distance energy of some special graphs. For example, it has been proved in [6–8] that(1)EDKn1,n2,…,nk=2∑i=1kni−k,where Kn1,n2,…,nk is a complete k-partite graph with the size of each partition being at least 2. The distance energy of some graphs with diameter 2 is also determined in [9]. Another interesting problem is to study how the distance energy of a graph changes by deleting an edge. Zhou and Ilić [10] showed that the deletion of any edge increases the distance energy of a connected graph with unique positive distance eigenvalue whenever the resulting graph is still connected. Varghese et al. [11] proved that EDKp,q<EDKp,q−e for any edge e of EKp,q, where Kp,q is a complete bipartite graph with p,q≥2. Recently, Tian et al. [12] showed that the deletion of any edge increases the distance energy of some special complete multipartite graphs.In this paper, we will give a new and shorter proof of the main result in [11] by transforming a problem on the sum of the absolute values of the roots of a quadratic polynomial into a problem on the largest root of a cubic polynomial.


## 2. Main Result

In this section, we will give a new and shorter proof onp,q≥2,EDKp,q<EDKp,q−e, which has been proved in [11]. Before giving our main proof, we need a result on distance eigenvalues of a graph.Lemma 1 (see [13]).
LetG be a graph of order n. If there exist k vertices having the same neighborhood, then G has distance eigenvalue −2 with multiplicity at least k−1.Next, we introduce a concept about the equitable quotient matrix. LetM be a symmetric matrix of order n whose block form is as follows:(2)M=M11⋯M1t⋮⋱⋮Mt1⋯Mtt,where the blocks Mij are ni×nj matrices for any 1≤i,j≤t and n=n1+⋯+nt. Let bij denote the sum of all entries in Mij divided by the number of rows. Then, BM=bij is called the quotient matrix of M. If Mij has a constant row sum for each pair (i,j), then B is called the equitable quotient matrix of M. Haemers [14] obtained the relation between the spectra of M and BM as follows.Lemma 2 (see [14]).
LetB be the equitable quotient matrix of M as defined above. Then, any eigenvalue of B is a eigenvalue of M.Now, we are ready to give the main result of this paper.Theorem 1.
For integersp,q≥2 and n=p+q,(3)EDKp,q<EDKp,q−e,where e is any edge of Kp,q.Proof.
Ifn=4 or 5, one can easily confirm that EDKp,q<EDKp,q−e holds; otherwise, n≥6. From the structure of the graph Kp,q−e, by Lemma 1, we found that the distance eigenvalues of Kp,q−e are −2 with multiplicity n−4. Note that, after relabeling the matrix DKp,q−e, we rewrite DKp,q−e as a 4×4 block matrix in the following form:(4)M=032J1,p−1J1,q−130J1,p−12J1,q−12Jp−1,1Jp−1,12Jp−1,p−1−2Ip−1Jp−1,q−1Jq−1,12Jq−1,1Jq−1,p−12Jq−1,q−1−2Iq−1,where Ji×j be a i×j matrix with all entries being 1. It is clear that each block of M has a constant row sum. Thus, the equitable quotient matrix of M is(5)B=032p−2q−130p−12q−1212p−2q−112p−12q−2.
After simple calculation, we obtain the characteristic polynomial ofB as(6)Px=x4−2n−4x3+3pq−12n+16x2+43pq−4n−4x+12n−5.
SinceP−2=−36pq+108p+108q−140≠0 for any integer p and q, Px=0 has four roots which are different from −2. Combining these results with Lemma 2, we conclude that DKp,q−e has eigenvalue −2 with multiplicity n−4 and the remaining four eigenvalues (say, λ1≥λ2≥λ3≥λ4) are the roots of Px=0. By Descartes’ rule of signs with the fact that ∑i=14λi=2n−8, one can easily check that λ1≥λ2>0>λ3≥λ4. Now, let a0,−a1,a2,a3,a4 be the coefficients of Px. Note that a0=1 and a4=12n−5. Then, Px can be rewritten as(7)x4−a1x3+a2x2+a3x+a4=x2−ax+bx2+cx+d,where a1=a−c, a2=b+d−ac, a3=bc−ad, and a4=bd.Claim 1.
λ1+λ2−λ3−λ42−a12>32n−64.Proof of Claim.
1. From the given conditions, we have(8)a+c2b−d2=a+c2b+d2−4bd=a+c2a2+ac2−4a4=a+c2a2+a+c2−a1242−4a4.
On the other hand, we have(9)a−cb+d=a1a2+ac=a1a2+a+c2−a124.
As2a3=2bc−ad, we obtain(10)2a3+a−cb+d=a+cb−d.
Combining (8)–(10), we can obtain that a+c2−a12 is the root of fy=0, where(11)fy=116y3+a22y2+a22−4a4−a1a3y−4a12a4−4a1a2a3−4a32.
From (7), it follows that a+c2 has three possible values:(12)λ1+λ2−λ3−λ42,λ1+λ3−λ2−λ42,λ1+λ4−λ2−λ32.
Sinceλ1≥λ2>0>λ3≥λ4, then λ1+λ2−λ3−λ42−a12 is the largest root of fy=0. Using the fact that a3=4a2+8n−20 and a4=12n−5, we have(13)fy=y−16a1−64a22+y22−4a1y−64a1+5122n−5a2+gn,y,a1,where(14)gn,y,a1=y316−162n−5a1+3n−15y−648n−202−48n−5a12.
Again using the fact thata1=2n−8, we obtain(15)f32n−64=128na2+gn,32n−64,2n−8=128na2−192n3+1984n2−2048n−1024.
Asp+q=n, it follows that a2≤3n2/4−12n+16. Combining the above results, we have(16)f32n−64≤128n3n24−12n+16−192n3+1984n2−2048n−1024=−32n−4n−23n+4<0.
This follows directly thatλ1+λ2−λ3−λ42−a12>32n−64. This completes the proof of Claim 1.
By Claim1 with a1=2n−8, we obtain(17)λ1+λ2−λ3−λ4>4n−42+32n−64=2n.
Hence, we have(18)EDKp,q−e=2n−4+λ1+λ2−λ3−λ4>4n−2=EDKp,q.
This completes the proof of this theorem.Remark 1.
It is worth mentioning that the method we used in the above proof would be a tool to compare the sum of the absolute values of the roots of a quadratic polynomial with a certain value.



---

*Source: 6678248-2021-01-09.xml*