# Spectral Properties with the Difference between Topological Indices in Graphs

Authors: Akbar Jahanbani; Roslan Hasni; Zhibin Du; Seyed Mahmoud Sheikholeslami
Journal: Journal of Mathematics
 (2020)

---

## Abstract

LetG be a graph of order n with vertices labeled as v1,v2,…,vn. Let di be the degree of the vertex vi, for i=1,2,…,n. The difference adjacency matrix of G is the square matrix of order n whose i,j entry is equal to di+dj−2−1/didj if the vertices vi and vj of G are adjacent or vivj∈EG and zero otherwise. Since this index is related to the degree of the vertices of the graph, our main tool will be an appropriate matrix, that is, a modification of the classical adjacency matrix involving the degrees of the vertices. In this paper, some properties of its characteristic polynomial are studied. We also investigate the difference energy of a graph. In addition, we establish some upper and lower bounds for this new energy of graph.


---

## Body

## 1. Introduction

LetG be a simple and connected graph with vertex set VG=v1,v2,…,vn and edge set EG. For i=1,2,…,n, di denotes the degree of vertex vi in G. If vi and vj are adjacent vertices in G, the edge connecting them is denoted by vivj. Graph theory has provided the chemists with a variety of useful tools, one of which is the topological indices. A topological index or graph invariant, for a graph, is a numeric quantity which is invariant under isomorphism of the graph. Usage of topological indices in chemistry began in 1947 when chemist Harold Wiener developed the most widely known topological descriptor, the Wiener number (later known as Wiener index), and used it to determine physical properties of types of alkanes known as paraffin [1].Furthermore, the difference betweenABC index and Randić index of a (molecular) graph G was introduced by Ali and Du [2] as follows:(1)ABC−RG=DG=∑uivj∈EGdi+dj−2−1didj.By equation (1), the difference between atom-bond connectivity index and Randić index (or difference index) of a graph G is defined as DG=di+dj−2−1/didj. The eigenvalues of the difference index DG are denoted by ϱ1,ϱ2,…,ϱn and are said to be the D-eigenvalues of G. We note that since the matrix of DG is symmetric, its eigenvalues are real and can be ordered as ϱ1≥ϱ2≥⋯≥ϱn.Some of the most popular topological indices are given as follows: the first Zagreb index usually denoted byM1 is defined as follows [3, 4]:(2)M1G=∑vi∈VGdi2,whereas the first Zagreb index satisfies the identity(3)M1G=∑vivj∈EGdi+dj.The modified second Zagreb indexℳ2∗G is equal to the sum of the reciprocal products of degrees of pairs of adjacent vertices [5], that is,(4)ℳ2∗G=∑vivj∈EG1didj.Ranjini et al. [6] redefined the Zagreb indices, i.e., the redefined first index for a graph G defined as(5)ReZG1G=∑vivj∈EGdi+djdidj.TheABC index was defined as follows [7]:(6)ABCG=∑vivj∈EGdi+dj−2didj.For the study of topological indices of graph associated with group, refer [8, 9] and the references therein.In mathematical chemistry, observe that all these topological indices are of the form(7)TI=TIG=∑vivj∈EGFdi,dj,where F is a pertinently chosen function with the property Fx,y=Fy,x. On each of such topological indices, a matrix TI can be associated, defined as(8)TIij=Fdi,dj,if the verticesviandvjofGare adjacent,0,other wise.There are several degree-based topological indices introduced to test the properties of compounds and drugs, which have been widely used in chemical and pharmacy engineering. Several matrices which are related to topological indices are given as follows:(i)
First Zagreb matrix [4]:(9)Z1ij=di+dj,if the verticesviandvjofGare adjacent,0,otherwise.(ii)
Albertson matrixA=aij [10]:(10)ALij=aij=di−dj,if the verticesviandvjofGare adjacent,0,otherwise.(iii)
Geometric-arithmetic matrix [11]:(11)GAij=2di×djdi+dj,if the verticesviandvjofGare adjacent,0,otherwise.(iv)
ABC matrix [12].(12)ABCij=di+dj−2didj,if the verticesviandvjofGare adjacent,0,otherwise.(v)
Sum-connectivity matrix [13]:(13)SCIij=1di+dj,if the verticesviandvjofGare adjacent,0,otherwise.In this paper, we would like to introduce the matrix associated with the difference between atom-bond connectivity index and Randic´ index of a graph G, defined as follows:(14)ABC−Rij=Dij=di,j=di+dj−2−1didj,if the verticesviandvjofGare adjacent,0,otherwise.We callD as the difference matrix associated with the difference between atom-bond connectivity index and Randić index of graph G.This paper is organized as follows: in Section2, we introduce some properties of characteristic polynomials of difference matrix and some properties of difference eigenvalues; in Section 3, we study the energy of graphs and introduce the difference energy; and we also obtain lower and upper bounds for this new energy.


## 2. Some Properties of Difference Matrix of Graphs

In this section, we introduce some properties of characteristic polynomials of difference matrix and some properties of difference eigenvalues of a graphG.LetG=V,E be a graph of order n with m edges and DG be the adjacency difference matrix with respect to a given degree. Suppose that(15)PG,ϱ:=detϱI−DG=a0ϱn+a1ϱn−1+a2ϱn−2+a3ϱn−3+⋯+an,is the characteristic polynomial of DG. Thus, in order to find nontrivial solutions to equation (15), one must demand that D−ϱI is not invertible, or equivalently,(16)PG,ϱ=PϱG=detDG−ϱI=0.Equation (16) is called the characteristic equation. Evaluating the determinant yields an n-th order polynomial in ϱ, called the characteristic polynomial, which we have denoted above by PG,ϱ.The determinant in equation (16) can be evaluated by the usual methods. It takes the following form:(17)PDG−ϱI=d11−ϱd12⋯d1nd21d22−ϱ⋯d2n⋮⋮⋱⋮dn1dn2⋯dnn−ϱ=a0ϱn+a1ϱn−1+a2ϱn−2+a3ϱn−3+⋯+an,where D=dij and dij are the vertices degree vi and vj.Now, we begin with the following example.Example 1.
The difference matrix of the graphG1 in Figure 1 is(18)DG1=000001500185−1125−1127−1200180005−11005−11200136−11505−11201306−115157−1205−1106−11506−115.Figure 1
A graphG1.The characteristic polynomial of the maximum degree matrixDG1 is(19)PDG1,ϱ=detDG1−ϱI=−ϱ0000150−ϱ185−1125−1127−120018−ϱ005−11005−1120−ϱ136−11505−112013−ϱ6−115157−1205−1106−1156−115−ϱ,and the difference eigenvalues of G1 are ϱ1=1.2619117684383,ϱ2=0.2094370173795,ϱ3=0.088080504528,ϱ4=−0.3333333333333,ϱ5=−0.746650631759,andϱ6=−0.4794453252535.Here, we compute some of the coefficients in equality (17).Lemma 1.
Leta0,a1,a2, and a3 be the coefficients in equality (17), then(20)ia0=1,iia1=0,iiia2=−∑1⩽i<j⩽ndi+dj−2−1didj2,iva3=−2P.Proof.
(i)
By the definition of the polynomial,(21)Pϱ:=detAϱ−ϱI,we geta0=1.(ii)
The sum of determinants of all1×1 principal submatrices of DG is equal to the trace of D implying that(22)a1=−11TrDG=0.(iii)
−12a2= sum of determinants of all the 2×2 principal submatrices of DG:(23)=∑1≤i<j≤ndiidijdjidjj=∑1≤i<j≤ndiidjj−dijdji=∑1≤i<j≤ndiidij−∑1≤i<j≤ndij2=−∑1≤i<j≤ndi+dj−2−1didj2,−13a3=∑1≤i<j<k≤ndiidijdikdjidjjdjkdkidkjdkk=−∑1≤i<j<k≤ndiiajjdkk−dkjajk−dijdjidkk−dkiajk+dikdjidkj−dkidjj=−∑1≤i<j<k≤ndiidjjdkk+∑1≤i<j<k≤ndiidkj2+djjdki2+dkkdij2+2∑1≤i<j<k≤ndkidjidjk=−2∑1≤i<j<k≤ndi+dj−2−1didjdi+dk−2−1didkdj+dk−2−1djdk=−2P,where P=∑1≤i<j<k≤ndi+dj−2−1/didjdi+dk−2−1/didkdj+dk−2−1/djdk.
We are dealing this part with some results related to the traces of powers ofD. Recall that we denote Nk=TrcDk. Now, we prove the following lemma that will need to obtain the main results.Lemma 2.
LetG be a graph with n vertices and difference matrix of D and ϱ1,ϱ2,…,ϱn be the eigenvalues of DG. Then,(24)1N0=∑i=1nϱi0=n,2N1=∑i=1nϱi=0,3N2=∑i=1nϱi2=2∑i∼jdi+dj−2−1didj2,4N3=∑i=1nϱi3=2∑i∼jdi+dj−2−1didj∑k∈VGk∼i,k∼jdi+dk−2−1didkdj+dk−2−1djdk,5N4=∑i=1nϱi4=∑i∈VG∑i∼jdi+dj−2−1didj2+∑i,j∈VGi≠j∑k∼i,k∼jdi+dk−2−1didkdj+dk−2−1djdk2,where ∑i∼j indicates summation over all pairs of adjacent vertices viandvj.Proof.
By definition, the diagonal elements ofD are equal to zero. Therefore, the trace of D is zero.
Next, we calculate the matrixD2. For i=j,(25)D2ii=∑j=1nDijDji=∑j=1nDij2=∑i∼jDij2=∑i∼jdi+dj−2−1didj2,whereas for i≠j,(26)D2ij=∑j=1nDijDji=DiiDij+DijDjj+∑k∈VGk∼i,k∼jDikDkj=∑k∈VGk∼i,k∼jDikDkjdi+dk−2−1didkdj+dk−2−1djdk.
Therefore,(27)trD2=∑i=1n∑i∼jdi+dj−2−1didj2=2∑i∼jdi+dj−2−1didj2.
Since the diagonal elements ofD3 are(28)D3ii=∑j=1nHijD2ji=∑i∼jdi+dj−2−1didj∑k∈VGk∼i,k∼jdi+dk−2−1didkdj+dk−2−1djdk,we have(29)trD3=∑i=1n∑i∼jdi+dj−2−1didj∑k∈VGk∼i,k∼jdi+dk−2−1didkdj+dk−2−1djdk=2∑i∼jdi+dj−2−1didj∑k∈VGk∼i,k∼jdi+dk−2−1didkdj+dk−2−1djdk.
We next calculateN4. The diagonal elements of D4 are(30)trD4=∑i∼jdi+dj−2−1didj2+∑j∈VGi≠j∑k∈VGk∼i,k∼jdi+dk−2−1didkdj+dk−2−1djdk2.
Then, we obtain(31)N4=∑i∈VG∑i∼jdi+dj−2−1didj2+∑i∈VGi≠j∑j∈VG∑k∼i,k∼jdi+dk−2−1didkdj+dk−2−1djdk2=∑i∈VG∑i∼jdi+dj−2−1didj2+∑i,j∈VGi≠j∑k∼i,k∼jdi+dk−2−1didkdj+dk−2−1djdk2.
This completes the proof.
Here, we recall the following lemma that we need to prove the next lemma.Lemma 3 (Rayleigh–Ritz [14]).
IfB is a real symmetric n×n matrix with eigenvalues λ1B≤λ2B≤⋯≤λnB, then for any X∈Rn, X≠0,(32)XtBX≤λ1BXtX.Equality holds if and only ifX is an eigenvector of B, corresponding to the largest eigenvalue λ1B.The following result is related with the large eigenvalueϱ1.Lemma 4.
LetG be a connected graph with n≥2 vertices. Then, the spectral radius of the difference matrix is bounded from below as(33)ϱ1≥2DGn.Proof.
LetD=dij be the difference matrix corresponding to D. By Lemma 3, for any vector X=x1,x2,…,xnt,(34)XtDX=∑j,j∼1nxjdj1,∑j,j∼2nxjdj2,…,∑j,j∼nnxjdjntX=2∑i∼jdijxixj,because dij=dji. Also,(35)XtX=∑i=1nxi2.
Using equations (34) and (35), by Lemma 3, we obtain(36)ϱ1≥2∑i∼jdijxixj∑i=1nxi2.
Since (36) is true for any vector X, by putting X=1,1,…,1t, we have(37)ϱ1≥2DGn.
This completes the proof.
Now, we obtain a lower bound for the maximum eigenvalue.Lemma 5.
LetG be a graph with n vertex and m edges:(38)ϱ1≥ABCGn−2mnδ.Proof.
Letx∈Rn be a unit vector, then(39)xTHx=∑uivj∈EGdu+dv−2−1dudvxixj=∑uivj∈EGdu+dv−2dudv−1dudvxixj=∑uivj∈EGdu+dv−2dudvxixj−∑uivj∈EG1dudvxixj≥∑uivj∈EGdu+dv−2dudvxixj−∑uivj∈EG1δxixj.
If we putxT=1/n,1/n,…,1/n, we get(40)xTHx≥∑uivj∈EGdu+dv−2ndudv−2mnδ=ABCGn−2mnδ.
Therefore, by Lemma3, the proof is now complete.
Here, we obtain an upper bound forN2 that will need to obtain upper and lower bounds for new energy.Lemma 6.
LetG be a simple graph with m edges and the redefined first ReZG1G index. Then,(41)N2≤2ReZ1G−22δ−2Δ2−ℳ2∗G.Proof.
By Lemma2, we know that(42)trD2=2∑uivj∈EGdi+dj−2−1didj2=2∑uivj∈EGdi+djdidj−2di+dj−2didj−1didj=2ReZ1G−∑uivj∈EG2di+dj−2didj−ℳ2∗G.
Now, since2δ≤di+dj≤2Δ for all edges vivj∈EG, δ≤di≤Δ for all vertices vi∈VG,(43)2ReZ1G−∑uivj∈EG2di+dj−2didj−ℳ2∗G≤2ReZ1G−22δ−2Δ2−ℳ2∗G.
This complete the proof.


## 3. Bounds for the Difference Energy of Graphs

In this section, we study the energy of graphs and introduce the difference energy. We also obtain lower and upper bounds for the new energy.The energyE=EG of a graph G is the sum of the absolute values of the eigenvalues of G. The motivation for the introduction of this invariant comes from chemistry, where results on E were obtained already in the 1940s. The graph energy is a graph-spectrum-based quantity, introduced in the 1970s. After a latent period of 20–30 years, it became a popular topic of research both in mathematical chemistry and in “pure” spectral graph theory. In 1978, Gutman defined energy mathematically for all graphs [15]. The energy of different graphs including regular, nonregular, circulant, and random graphs is also under study. The energy of the graph G is defined as(44)E=EG=∑i=1nλi,where λi, i=1,2,…,n, are the eigenvalues of graph G.The difference energy (ED energy) of the graph G is defined in an analogue way as(45)EDG=∑i=1nϱi.It is usual and useful to define some modified energies such as Zagreb energy, harmonic energy, Albertson energy, matching energy, Laplacian energy, and geometric-arithmetic energy (refer [16–18] and [10, 19–26]). These modified energies have applications in theoretical organic chemistry [27], image processing [28], and information theory [29].Example 2.
The difference energy of the graphG1 in Figure 1 is(46)EDG1=3.1188585806916.
We start with upper bound for difference energy.Theorem 1.
LetG be a graph with n vertices. Then,(47)EDG≤2nREZ1G−22δ−2Δ2−ℳ2∗G.Proof.
By Cauchy Schwarz inequality and Lemma6, we have(48)∑i=1nϱ≤n∑i=1nϱ2≤2nREZ1G−22δ−2Δ2−ℳ2∗G.
Hence,(49)EDG≤2nREZ1G−22δ−2Δ2−ℳ2∗G.
This completes the proof.
We need the following lemma to obtain lower and upper bounds of the difference energy involvingN2.Lemma 7 (see [30]).
Leta1,…,an and b1,…,bn be real numbers such that a≤ai≤A and b≤bi≤B, i=1,…,n. Then,(50)−A−aB−bnαn≤∑i=1naibi−1n∑i=1nai∑i=1nbi≤A−aB−bnαn,where αn=1/41−−1n+1+1/2n2.Here, we obtain lower and upper bounds for new energy.Theorem 2.
LetG be a graph with n vertices. Then,(51)nN2−n2αnϱ1−ϱn2≤EDG≤nN2+n2αnϱ1−ϱn2.Equality holds if and only ifG≅G¯.Proof.
Forai=bi:=ϱi, A=B:=ϱ1, a=b:=ϱn, and M2=m2:=1, inequality (50) becomes(52)−ϱ1−ϱnϱ1−ϱnnαn≤∑i=1nϱi2−1n∑i=1nϱi∑i=1nϱi≤ϱ1−ϱnϱ1−ϱnnαn.
Therefore, by Lemma2 and definition of difference energy, inequality (52) becomes(53)−nαnϱ1−ϱn2−N2≤−1nED2G≤nαnϱ1−ϱn2−N2.
Clearly, ifG≅G¯, then ϱ1=ϱ2=⋯=ϱn=0; hence, EDG=0, and also, nN2=0; therefore by (51), we have 0=EDG=0. Conversely, if equality holds on both sides of (51), then equality holds in (52) and (53); therefore, we have(54)−nαnϱ1−ϱn2−N2=−1nED2G=nαnϱ1−ϱn2−N2.
So by equality on both sides of (54), we get nαnϱ1−ϱn2=0, since n,α≠0, therefore, ϱ1−ϱn2=ϱ1−ϱn2=0; in other words, ϱ1=ϱn or ϱn=±ϱ1; hence, ϱ1=ϱn=0, then G≅G¯.
Now, we obtain lower bound for new energy involvingN2 and N3.Theorem 3.
LetG be a graph with n vertices and at least one edge. Then,(55)EDG>N23N4.Proof.
Using Ho¨lder inequality, we have(56)∑i=1naiv≤∑i=1naip1/p∑i=1naiq1/q,which holds for any nonnegative real numbers ai,bi,i=1,2,…,n. Setting ai=ϱi2/3,bi=ϱi4/3,p=3/2, and q=3, we obtain(57)∑i=1nϱi2=∑i=1nϱi2/3∑i=1nϱi4/3≤∑i=1nϱi2/3∑i=1nϱi41/3,since G is nonempty graph; hence, we have(58)∑i=1nϱi>∑i=1nϱi23∑i=1nϱi4=trD23trD4=N23N4.
Hence, we get the result.
Now, we obtain an upper bound for new energy involving vertices, edges, minimum degree, andABC index.Theorem 4.
LetG be a nonempty graph with n vertices. Then,(59)EDG<ABCGn−2mnδ+n−1N2−ABCGn−2mnδ2.Proof.
Letϱ1≥ϱ2≥⋯≥ϱn−1≥ϱn be the eigenvalues of G. By the Cauchy–Schwartz inequality,(60)∑i=1nϱi≤n−1∑i=2nϱi2=n−1N2−ϱ12.
Hence,(61)EDG≤ϱ1+n−1N2−ϱ12.
Note that the functionfx=x+n−1N2−x2 decreases for ABCG/n−2m/nδ≤x≤ABCG/n2−2m/nδ. By Lemma 5, we have ϱ1≥ABCG/n−2m/nδ; therefore,(62)ϱ1≥ABCGn−2mnδ≥ABCGn2−2mnδ.
Sofϱ1G≤fABCG/n−2m/nδ, since G is nonempty graph which implies that(63)EDG<ABCGn−2mnδ+n−1N2−ABCGn−2mnδ2.
This completes the proof.
Similarly, by Lemma4, we have the following lemma.Lemma 8.
LetG be a nonempty graph with n vertices:(64)EDG≤2DGn+n−1N2−2DGn2.Here, we obtain an upper bound for new energy involving vertices andN2.Theorem 5.
LetG be a graph with n vertices. Then,(65)EDG≤N2+n2.Equality holds if and only ifG≅n/2K2,n=2m.Proof.
Leta1,a2,…,an and b1,b2,…,bn be sequences of real numbers and c1,c2,…,cn and d1,d2,…,dn are nonnegative. Then, the following inequality is valid (see [31]):(66)∑i=1ndi∑i=1nciai2+∑i=1nci∑i=1ndibi2≥2∑i=1naici∑i=1nbidi.
Forai:=ϱi, bi:=ci=di=1, i=1,2,…,n, inequality (66) becomes(67)∑i=1n1∑i=1nϱi2+∑i=1n1∑i=1n1≥2∑i=1nϱi∑i=1n1.
Therefore, by Lemma2, we have(68)EDG≤N2+n2.
IfG≅n/2K2, then it is easy to check that the equality in (65) holds. Conversely, if the equality in (65), then equality holds in (66) and (67); therefore, we have(69)∑i=1n1∑i=1nϱi2+∑i=1n1∑i=1n1=2∑i=1nϱi∑i=1n1.
Hence, we have(70)∑i=1nϱi2+n=2∑i=1nϱi.
By using equality (70), we get(71)2ϱ1+ϱ2+⋯+ϱn−ϱ12+ϱ22+⋯+ϱn2=n.
Hence, by equality (71), we have(72)ϱ1=ϱ2=⋯=ϱn=1.
Therefore,G≅n/2K2,n=2m.
Now, we obtain a lower bound for new energy involving maximum eigenvalue andN2.Theorem 6.
LetG be a nonempty graph with n≥2 vertices. Then,(73)EDG≥N2ϱ1.Equality holds if and only ifG≅n/2K2,n=2m.Proof.
Letaiandbi be decreasing nonnegative sequences with a1,b1≠0 and wi a nonnegative sequence, for i=1,2,…,n. Then, the following inequality is valid (see [32] p. 85):(74)∑i=1nwiai2∑i=1nwibi2≤maxb1∑i=1nwiai,a1∑i=1nwibi∑i=1nwiaibi.
Forai=bi:=ϱi and wi:=1, i=1,2,…,n, inequality (74) becomes(75)∑i=1nϱi2∑i=1nϱi2≤maxϱ1∑i=1nϱi,ϱ1∑i=1nϱi∑i=1nϱi2.
Since(76)∑i=1nϱi2=∑i=1nϱi2=N2,∑i=1nϱi=EDG,then the above inequality follows directly from the assertion of Theorem 6, i.e., inequality (73).
IfG≅n/2K2, then it is easy to check that the equality in (73) holds. Conversely, if the equality in (73) hold, then equality also holds in (74) and (75); therefore, we have(77)∑i=1nϱi2∑i=1nϱi2=maxϱ1∑i=1nϱi,ϱ1∑i=1nϱi∑i=1nϱi2.
From equality (77), we get(78)∑i=1nϱi2=σ1∑i=1nϱi.
By equality (78), we have(79)ϱ12+ϱ22+⋯+ϱn2−ϱ1ϱ1+ϱ2+⋯+ϱn=0.
Equality (79) implies that(80)ϱ1+ϱ2+⋯+ϱnϱ1+ϱ2+⋯+ϱn−ϱ11+1+⋯+1︸ntimes=0.
SinceG is a nonempty graph, then ϱ1+ϱ2+⋯+ϱn=EDG≠0; therefore, by equality (80), we have(81)ϱ1+ϱ2+⋯+ϱn=ϱ11+1+⋯+1︸ntimes.
Hence, we haveϱ1=ϱ2=⋯=ϱn=1. Therefore, G≅n/2K2,n=2m.
Analogy with the paper [24], we obtain the following theorems.Theorem 7.
LetG be a graph with n vertices. Then,(82)N2≤EDG≤nN2.Theorem 8.
LetG be a connected graph with n vertices. Then,(83)EDG≥N2+nn−1detD2/n.


## 4. Conclusion

In this paper, the spectral properties of the difference between the atom-bond connectivity index and Randić index were studied. Our main tool was the modification of the classical adjacency matrix involving the degree of the vertices in graphG. Some properties of its characteristic polynomial were established. In addition, bounds for the difference energy were obtained, as well as the relations between them.



---

*Source: 6973078-2020-07-26.xml*