# Nordhaus–Gaddum-Type Relations for Arithmetic-Geometric Spectral Radius and Energy

Authors: Yajing Wang; Yubin Gao
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

Spectral graph theory plays an important role in engineering. LetG be a simple graph of order n with vertex set V=v1,v2,…,vn. For vi∈V, the degree of the vertex vi, denoted by di, is the number of the vertices adjacent to vi. The arithmetic-geometric adjacency matrix AagG of G is defined as the n×n matrix whose i,j entry is equal to di+dj/2didj if the vertices vi and vj are adjacent and 0 otherwise. The arithmetic-geometric spectral radius and arithmetic-geometric energy of G are the spectral radius and energy of its arithmetic-geometric adjacency matrix, respectively. In this paper, some new upper bounds on arithmetic-geometric energy are obtained. In addition, we present the Nordhaus–Gaddum-type relations for arithmetic-geometric spectral radius and arithmetic-geometric energy and characterize corresponding extremal graphs.


---

## Body

## 1. Introduction

Spectral properties of graphs have been widely applied in the field of engineering technology. In systems engineering, complex networks are often used as abstract models to study and reveal the relationship among system elements. The mathematical study of complex network depends on graph theory. In network dynamics, the analysis of threshold in the epidemic model and synchronization condition of coupling oscillators is essentially the study of spectral of the corresponding graph. Naturally, the development of systems engineering depends on the results and conclusions of basic studies in graph spectral theory. Similarly, in the chemical engineering, a chemical molecule can also be abstracted as a graph. The combinatorial forms of spectral of weighted graphs, based on topological indices, are closely related to the molecular orbital energy levels ofπ-electrons in conjugated hydrocarbons, as well as the spectrum properties. The combinatorial form of the spectrum, significantly correlated with the stability of conjugated alternant molecules, is defined as the sum of the absolute values of the eigenvalues of graphs. In this paper, we further study the arithmetic-geometric spectral radius and arithmetic-geometric energy.LetG=V,E be a simple graph with vertex set V=v1,v2,…,vn and edge set E, and let E=m. An edge e∈E with end vertices vi and vj is denoted by vivj. The degree of the vertex vi∈V of G for i=1,2,…,n is denoted by di. Let Δ and δ represent the maximum and minimum degrees of G, respectively. The graph G¯ is called the complement to the graph G, if its vertex set is the same as V, and vi and vji,j=1,2,…,n,i≠j are adjacent in G¯ if and only if they are not adjacent in G.The adjacency matrix of a graphG is the matrix aijn×n, denoted by AG, where aij=1 if vi and vj are adjacent; if not, aij=0. All eigenvalues of AG are denoted by the nonincreasing sequence λ1,λ2,…,λn. The spectral radius of G is the greatest eigenvalue λ1. The energy of G is defined as(1)ℰG=∑i=1nλiG.As a graph invariant, topological indices are used to understand physicochemical properties of chemical compounds since they capture some properties of molecules. In 2015, the paper [1] proposed the arithmetic-geometric index of a graph G and defined the arithmetic-geometric adjacency matrix (AG matrix) of G, denoted by AagG. An element of AG matrix is defined in the following manner:(2)gij=di+dj2didj,ifvivj∈E,0,otherwise.The AG eigenvalues ofG are the eigenvalues of its corresponding AG matrix. Note that AG matrix is real and symmetric so that all eigenvalues of AagG are real, which can be recorded as η1≥η2≥⋯≥ηn. Similarly, the greatest AG eigenvalue η1 is called the arithmetic-geometric spectral radius (AG spectral radius) of G. In addition, the arithmetic-geometric energy (AG energy) of G is defined in an analogue way as(3)ℰagG=∑i=1nηi.The first Zagreb indexM1G is a kind of important topological indices, which is defined in [2] as(4)M1G=∑i=1ndi2=∑vivj∈EGdi+dj.A graphG is said to be strongly regular with parameters n,r,μ,ν if it is r−regular, every pair of adjacent vertices has μ≥0 common neighbors, and every pair of distinct nonadjacent vertices has ν≥0 common neighbors [3]. If ν=0, then G is a disjoint union of complete graphs, whereas if ν≥1 and G is noncomplete, then the eigenvalues of G are r (the trivial eigenvalue) and the roots x1 and x2 (the nontrivial eigenvalues) of the quadratic equation:(5)x2+ν−μx+ν−r=0.It is straightforward to show that the complement of a strong regular graph with parametersn,r,μ,ν is still a strong regular graph with parameters n,n−1−r,n−2−2r+ν,n−2r+μ. Recently, some bounds on AG spectral radius and AG energy were obtained in a couple of papers [4, 5]. Until now, hundreds of such “energy” have been introduced, such as inverse sum index energy [6], distance energy [7, 8], ABC energy [9, 10], matching energy [11, 12], and Randić energy [13, 14]. Recently, there are many studies, such as [15–17], on the energy of graphs with given parameters.In the paper of Nordhaus and Gaddum [18], the lower and upper bounds on χG+χG¯ and χG⋅χG¯ were given, where χG and χG¯ were the chromatic number of a graph G and its complement G¯, separately. Since then, in terms of an invariant ψG of graph G, any bound on ψG+ψG¯ or ψG⋅ψG¯ is referred to as a Nordhaus–Gaddum-type inequality or relation. And Nordhaus–Gaddum-type relations have received wide attention (e.g., [19]).We writeG1≅G2 if the graphs G1 and G2 are isomorphic. As usual, let Kn denote the complete graph of order n and Kp1,p2,…,pn the complete multipartite graph, having pi vertices in the ith partite set for each i=1,2,…,n. Thus, Kn≅Kp1,p2,…,pn, where p1=p2=⋯=pn=1. For other undefined notions and terminologies from graph theory, the readers are referred to [20, 21]. The rest of the paper is structured as follows: in Section 2, we give some useful lemmas; in Section 3, we get some new bounds on the AG energy; and in Sections 4 and 5, we obtain the Nordhaus–Gaddum-type relations for the AG spectral radius and AG energy of graph G, respectively.


## 2. Preliminaries

Lemma 1.
(see [22]). If B is an n×n real symmetric matrix with eigenvalues λ1≥λ2≥⋯≥λn, then for any 0≠x∈Rn, xTBx≤λ1xTx. Equality holds if and only if x is an eigenvector of B corresponding to λ1.Lemma 2.
(see [23]). Let G be a graph of order n and size m with maximum degree Δ and minimum degree δ≥1. Then,(6)λ1≤2m−δn−1+δ−1Δ,with equality holding if and only if G is regular, a star plus copies of K2, or a complete graph plus a regular graph with a smaller degree of vertices.Lemma 3.
(see [5]). Let G be a graph of order n with the maximum degree Δ and minimum degree δ≥1. Then,(7)η1≤12Δδ+δΔλ1,with equality holding if and only if G is regular.Lemma 4.
(see [5]). Let G be a graph of order n. Then,(8)η1≥M1Gn,with equality holding if and only if G is regular.Lemma 5.
(see [24]). A connected graph G of order n has only one positive eigenvalue in its adjacency spectrum if and only if G is a complete multipartite graph.


## 3. On AG Energy of a Graph

Lemma 6.
LetG be a graph of order n and size m, then(9)η1≥2mn,equality holds if and only if G is a regular graph.Proof.
Let us take any unit vectorx=x1,x2,…,xnT in Rn. By Lemma 1, we have(10)η1≥xTAagGx=∑vivj∈EGdi+djdidjxixj≥2∑vivj∈EGxixj.
Takingx=1/n,1/n,…,1/nT into (10), we have(11)η1G≥xTAagGx≥2mn,then (9) holds.
For the equality in (9) to hold, all the inequalities in the above argument must be equalities. From (10), we have d1=d2=⋯=dn. Then, G is a regular graph.
Conversely, ifG is regular, then d1=d2=⋯=dn. So x=1/n,1/n,…,1/nT is an eigenvector of AagG corresponding to the eigenvalue η1. Then, the equality holds in (9).Theorem 1.
LetG be a graph of order n and size m, then(12)ℰagG≥4mn,with equality holding if and only if G is isomorphic to a regular complete multipartite graph or G≅K¯n.Proof.
Applying Lemma6, we have(13)ℰagG=∑i=1nηi=2∑i=1,ηi≥0nηi≥2η1≥4mn.
The first equality attained if and only ifG has at most one positive AG eigenvalue, and the second equality holds if and only if G is regular. If G has no positive eigenvalue, then G≅K¯n. If G has only one positive eigenvalue, from Lemma 5, then G is isomorphic to a complete multipartite graph. And, if G is a regular graph, then its AG matrix is identical to its adjacency matrix. If so, we know that the equality in Theorem 1 holds if and only if G is isomorphic to a regular complete multipartite graph, or G≅K¯n.Theorem 2.
LetG be a graph of order n and size m, and δ>0. Then,(14)ℰagG≤t+n−1m2Δδ+δΔ2−t2,where t=max2m/n,Δ/δ+δ/Δm/2n. This bound is achieved if G is either n/2K2, Kn, or a noncomplete connected strongly regular graph with two nontrivial eigenvalues both with absolute value:(15)2m−2m/n2n−1.Proof.
By Lemma6, we have η1≥2m/n. Moreover, since(16)∑i=1nηi2=12∑vivj∈EGdi+djdidj2=12∑vivj∈EGdidj+djdi2≤12∑vivj∈EGΔδ+δΔ2=m2Δδ+δΔ2must hold, we have(17)∑i=2nηi2≤m2Δδ+δΔ2−η12.
Combining the above inequality with the Cauchy–Schwartz inequality, we can see that the following inequality is obvious:(18)∑i=2nηi≤n−1m2Δδ+δΔ2−η12.
Thus,(19)ℰagG≤η1+n−1m2Δδ+δΔ2−η12.
Since the function(20)Fx=x+n−1m2Δδ+δΔ2−x2reaches the maximum for x=Δ/δ+δ/Δm/2n, we see that Fη1≤FΔ/δ+δ/Δm/2n must hold as well. In addition, if 2m/n≥Δ/δ+δ/Δm/2n, then Fη1≤F2m/n. From this fact and inequality (19), it immediately follows that inequality (14) holds when t=max2m/n,Δ/δ+δ/Δm/2n.
It is obvious that2m≥n and we know that if G is either n/2K2, Kn, or a noncomplete connected strongly regular graph, the inequality 2m/n≥Δ/δ+δ/Δm/2n holds. As the graph n/2K2 is regular, its AG matrix is the same as its adjacency matrix. That is to say, the AG eigenvalues for n/2K2 are ±1 (both with multiplicity n/2). Similarly, the AG eigenvalues for Kn are n−1 (multiplicity 1) and −1 (multiplicity n−1) so that equality must hold in (14), if G is isomorphic to n/2K2 or Kn.
Moreover, ifG is a noncomplete connected strongly regular graph with the trivial eigenvalue 2m/n and other two nontrivial eigenvalues both with absolute value 2m−2m/n2/n−1, the equality holds in (14) as well.Remark 1.
The paper [4] proved that if G is a simple graph of order n and size m having no isolated vertices, then the following bound must hold:(21)ℰagG≤Δδ2mn.
The reason is following:Fx defined in the proof of Theorem 2 reaches the maximum for x=Δ/δ+δ/Δm/2n, and the maximum is Fx=1/2Δ/δ+δ/Δ2mn. It follows that(22)ℰagG≤12Δδ+δΔ2mnmust hold. Moreover, 1/2Δ/δ+δ/Δ2mn≤Δ/δ2mn. Hence, inequality (14) is an improvement on the bound in [4].Theorem 3.
If2m≤n and G is a graph on n vertices with m edges, then(23)ℰagG≤mΔΓδΓ+δΓΔΓ,where Γ is the graph obtained from G by deleting all isolated vertices. Equality holds if and only if Γ≅n/2K2.Proof.
It is easy to know thatG has at least n−2m isolated vertices if 2m≤n. We can obtain a graph Γ with no isolated vertices by removing all isolated vertices. It follows that Γ has at most 2m vertices. Hence, by applying inequality (22) to Γ, we can immediately see that(24)ℰagG≤12ΔΓδΓ+δΓΔΓ2mn≤mΔΓδΓ+δΓΔΓ.
Moreover, equality holds if and only if2m=n; that is, G is the disjoint union of edges.Theorem 4.
LetG be a graph of order n and size m and δ>0. Then,(25)ℰagG≤n+nn8Δδ+δΔ2,holds. If G is a strongly regular graph with parameters n,n+n/2,n+2n/4,n+2n/4, the bound is achieved.Proof.
It is obvious that2m≥n. If 2m/n≥Δ/δ+δ/Δm/2n, then the inequality (14) is as follows:(26)ℰagG≤2mn+n−1m2Δδ+δΔ2−2mn2.
Using routine calculus, it is seen that the left-hand side of inequality (26)—considered as a function of m—is maximized when(27)m=n2+nn16Δδ+δΔ2,holds. Inequality (25) now follows by substituting this value of m into (26).
IfΔ/δ+δ/Δm/2n≥2m/n, then by inequality (22) and 2m≥n, we know that(28)ℰagG≤n4Δδ+δΔ2.
Sincen+nn/8Δ/δ+δ/Δ2>n/4Δ/δ+δ/Δ2, then it is clear that (25) follows. Moreover, it follows by Theorem 2 that if G is a strongly regular graph with parameters n,n+n/2,n+2n/4,n+2n/4, equality holds in (25), which means that the upper bound is achieved. The theorem follows.


## 4. Nordhaus–Gaddum-Type Relation for AG Spectral Radius

LetΔ¯, δ¯, and η¯1 be the maximum degree, minimum degree, and spectral radius of the complement graph G¯ of G, respectively. Here, we are presenting the lower and upper bounds on η1+η1¯.Theorem 5.
LetG be a graph of order n. Then,(29)η1+η¯1≥M1Gn+M1G¯n,and the equality holds if and only if G is a regular graph.Proof.
The proof of inequality in (29) follows directly from Lemma 4.
If the equality in (29) holds, that is, η1=M1G/n and η¯1=M1G¯/n, then by Lemma 4, G is regular.
IfG is a regular graph, then(30)η1+η¯1=Δ+n−1−δ=n−1=M1Gn+M1G¯n.
This finishes the proof.Theorem 6.
LetG be a graph of order n. Then,(31)η1+η¯1≥n−1,with equality holding if and only if G is a regular graph.Proof.
Lemma6 gives that(32)η1≥2mn,η¯1≥2EG¯n,where EG¯ denotes the number of edges in G¯. Then, we have(33)η1+η¯1≥2mn+2EG¯n=2nn2=n−1.
From Lemma6, equality holds if and only if G is isomorphic to a regular graph.Theorem 7.
LetG be a connected graph of order n and size m. And we write the number of vertices with di=Δ by t and the second largest degree of graph G by τ:(1)
IfΔ=n−1 or Δ¯=n−1, then(34)η1+η¯1≤12n−1δ+δn−12m−n+1+12n−t−1n−1−τ+n−1−τn−t−1n−12−2m+t.(2)
IfΔ≤n−2 and Δ¯≤n−2, then(35)η1+η¯1≤12Δδ+δΔ2m−δn−1+δ−1Δ+12n−1−δn−1−Δ+n−1−Δn−1−δn−12−2m−δn−2−Δ.Moreover, the bounds are sharp.Proof.
(1) Without loss of generality, letΔ=n−1. Since δ≥1, by Lemmas 2 and 3, we have(36)η1≤12n−1δ+δn−12m−δn−1+δ−1n−1=12n−1δ+δn−12m−n+1.
It clearly follows thatG¯ has t isolated vertices. Let Γ1 be the graph obtained from G¯ by removing the isolated vertices. It is clear that η¯1=η1Γ1, Δ¯=ΔΓ1≤n−t−1, and δ¯=δΓ1=n−1−τ, so(37)η¯1≤12ΔΓ1δΓ1+δΓ1ΔΓ12eΓ1−δΓ1VΓ1−1+δΓ1−1ΔΓ1≤12n−t−1n−1−τ+n−1−τn−t−12n2−2m−n−t−1=12n−t−1n−1−τ+n−1−τn−t−1n−12−2m+t.
The proof of the inequality (34) follows.
(2) LetΔ≤n−2 and Δ¯≤n−2. It follows that δ≥1 and δ¯≥1. From Lemmas 2 and 3, we have(38)η1≤12Δδ+δΔ2m−δn−1+δ−1Δ,η¯1≤12Δ¯δ¯+δ¯Δ¯2n2−2m−δ¯n−1+δ¯−1Δ¯=12n−1−δn−1−Δ+n−1−Δn−1−δ2n2−2m−n−1−Δn−1+n−2−Δn−1−δ=12n−1−δn−1−Δ+n−1−Δn−1−δn−12−2m−δn−2−Δ.
Hence, the inequality (35) holds.
To show the sharpness of upper bounds in Theorem7, we consider the following examples.Example 1.
LetG be a star of order n. That is to say, t=1 and τ=1. Then, G¯ is the union of an isolated vertex and a complete graph Kn−1. We have(39)η1=n2=12n−1+1n−1n−1=12n−1δ+δn−12m−n+1,η¯1=n−2=12n−t−1n−1−τ+n−1−τn−t−1n−12−2m+t.Example 2.
LetG be a regular graph. It is clear that G¯ is still a regular graph. We have(40)η1+η¯1=Δ+n−1−Δ=n−1=12Δδ+δΔ2m−δn−1+δ−1Δ+12n−1−δn−1−Δ+n−1−Δn−1−δn−12−2m−δn−2−Δ.


## 5. Nordhaus–Gaddum-Type Relation for AG Energy

In the following theorems, some lower and upper bounds forℰagG+ℰagG¯ are obtained.Theorem 8.
LetG be a connected graph of order n and size m and Γ1,Γ2,…,Γr be all connected components of G¯. Then,(41)ℰagG+ℰagG¯≥4mn+∑i=1r4EΓiVΓi,where VΓi and EΓi are the number of vertices and edges in Γii=1,…,r, respectively. Moreover, the equality holds if and only if G is isomorphic to a regular complete multipartite graph, or G≅K¯n.Proof.
Applying Theorem1, we have(42)ℰagG≥4mn,ℰagΓi≥4EΓiVΓi.
Hence, we can obtain(43)ℰagG+ℰagG¯=ℰagG+∑i=1rℰagΓi≥4mn+∑i=1r4EΓiVΓi.
From Theorem1, we know that equality is possible if and only if G is isomorphic to regular complete multipartite graph, or G≅K¯n. The complement of regular complete multipartite graph is the disjoint union of k complete graphs of order n/k, and Kn is the complement graph of K¯n. If so, ℰagΓi=4EΓi/VΓi holds. Hence, the equality holds if and only if G is isomorphic to a regular complete multipartite graph, or G≅K¯n.Theorem 9.
LetG be a graph of order n and size m, then(44)ℰagG+ℰagG¯≥2n−1,with equality holding if and only if either G≅Kn or G≅K¯n.Proof.
Note that(45)ℰagG+ℰagG¯≥4mn+4EG¯n=4nn2=2n−1.
Similar to the analysis of equality in Theorem8, we consider the following two cases:(1)
G≅Kn, which implies G¯≅K¯n.(2)
BothG and G¯ are isomorphic to regular complete multipartite graphs. This is impossible because complete multipartite graphs are connected, whereas their complements are disconnected.Theorem 10.
LetG be a graph of order n and G¯ is the complement graph of G. If both G and G¯ have no isolated vertices, then(46)ℰagG+ℰagG¯≤n+nn4Δn−1−δδn−1−Δ+3.IfG is a strongly regular graph with parameters n,n+n/2,n+2n/4,n+2n/4, the equality holds.Proof.
From Theorem4, we have(47)ℰagG+ℰagG¯≤n+nn8Δδ+δΔ2+n+nn8Δ¯δ¯+δ¯Δ¯2=n+nn8Δδ+δΔ2+n−1−δn−1−Δ+n−1−Δn−1−δ2≤n+nn4Δn−1−δδn−1−Δ+3.
IfG is a strongly regular graph, we know that G¯ is also a strongly regular graph. Moreover, all inequalities in the above argument must be equalities. The first equality holds if G is isomorphic to a strongly regular graph with parameters n,n+n/2,n+2n/4,n+2n/4. And, the last equality holds if G is regular. The theorem now follows immediately.


## 6. Conclusions

In this paper, we obtain an upper bound on AG spectral radius, and furthermore, the Nordhaus–Gaddum-type relation of AG spectral radius is derived. Some new upper and lower bounds on arithmetic-geometric energy are obtained. Moreover, we illustrate one of the upper bounds is better than the result in paper [4]. In the end, we state the Nordhaus–Gaddum-type relation of AG energy.



---

*Source: 5898735-2020-07-16.xml*