# The Maximal ABC Index of the Corona of Two Graphs

Authors: Haiqin Liu; Yanling Shao
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

LetG1∘G2 be the corona of two graphs G1 and G2 which is the graph obtained by taking one copy of G1 and VG1 copies of G2 and then joining the ith vertex of G1 to every vertex in the ith copy of G2. The atom-bond connectivity index (ABC index) of a graph G is defined as ABCG=∑uv∈EGdGu+dGv−2/dGudGv, where EG is the edge set of G and dGu and dGv are degrees of vertices u and v, respectively. For the ABC indices of G1∘G2 with G1 and G2 being connected graphs, we get the following results. (1) Let G1 and G2 be connected graphs. The ABC index of G1∘G2 attains the maximum value if and only if both G1 and G2 are complete graphs. If the ABC index of G1∘G2 attains the minimum value, then G1 and G2 must be trees. (2) Let T1 and T2 be trees. Then, the ABC index of T1∘T2 attains the maximum value if and only if T1 is a path and T2 is a star.


---

## Body

## 1. Introduction

Graph theory has been applied in many engineering fields such as mechanical design and manufacturing and chemical engineering. In the graph theory, the link in the mechanism can be regarded as the vertex, kinematic pair can be regarded as an edge, and then the topological configuration of the mechanism is abstracted as the graph. Therefore, the nature and characteristics of the mechanism can be analyzed by relevant graph theory. In chemical engineering, if a chemical molecule is regarded as a two-dimensional graph, the graph’s vertices represent atoms, and edges represent chemical bonds, then the graph determines the topological properties of the given molecule.Molecular descriptors play an important role in chemistry and pharmacology. Among these molecular descriptors, so-called topological indices play a significant role. Topological indices are the mathematical tools that correlate the chemical structure with various physical properties, chemical reactivity, or biological activity numerically. And the topological indices have been widely applied in the study of the stability of alkanes and the strain energy of cycloalkanes. In the field of pharmaceutical chemistry and bioinformatics, topological index can be used to encode the chemical structure. This encode strategy provides the annotation, comparison, rapid collection, mining, and retrieval of chemical structures within large databases. Afterward, topological indices can be used to look for quantitative structure-activity relationships and quantitative structure-property relationships. In QSAR/QSPR studies, the biological activities of compounds can be predicted according to their topological indices, such as Zagreb, Randic, and the atom-bond connectivity indices.The topological indices can be classified by the structural properties of graphs used for their calculation. The atom-bond connectivity index, which was proposed by Estrada et al. in 1998, is a vertex-degree-based graph topological index.We consider finite undirected connected graphs without loops or multiple edges. LetG1 and G2 be two such graphs. The corona of G1 and G2, denoted by G1∘G2, is defined as the graph obtained by taking one copy of G1 and VG1 copies of G2 and then joining the ith vertex of G1 to every vertex in the ith copy of G2 (as shown in Figure 1). Corona graphs were introduced by Frucht and Harary in 1970 [1].Figure 1
CoronaG1∘G2 of G1 and G2. (a) G1. (b) G2. (c) G1∘G2.
(a)(b)(c)LetG=V,E be a connected graph with vertex set V=VG and arc set E=EG. The atom-bond connectivity index (ABC index) of G is defined as(1)ABCG=∑uv∈EGdGu+dGv−2dGudGv,where dGu (or du) and dGv (or dv) are degrees of vertices u and v, respectively.LetG be a graph. For an edge e=uv∈EG and an edge set E0⊆EG, denote(2)ABCGe=du+dv−2dudv,ABCGE0=∑e∈E0ABCGe.We say thatABCGe is the ABC index of e and ABCGE0 is the ABC index of E0.Throughout the paper, we useKn, Sn, and Pn to denote the complete graph, the star, and the path of order n, respectively.The ABC index attracted a lot of attention in the last few years. Several properties of ABC index were established. In particular, if a new edge is inserted intoG, then ABC index necessarily increases (see Lemma 1).Lemma 1 (see [2]).
LetG be a simple graph with nonadjacent vertices i and j. Then,(3)ABCG+ij>ABCG.It is evident thatKn has the maximal ABC index, whereas the connected graph with the minimal ABC index must be a tree (see [2, 3]). The smallest ABC index of trees with n pendant vertices was characterized in [4]. In contrast to the minimal case, the tree with the maximal ABC index was easily identified as the star (see [5]). In [6], the maximum and minimum ABC indices of all unicyclic graphs and unicyclic chemical graphs were obtained, and the corresponding extremal graphs were also characterized. In [7, 8], the maximum values of the ABC indices in the class of all n-vertex bicyclic and tricyclic graphs were presented, respectively.Recently, some researchers have paid more attention to the ABC spectral radius which is associated with ABC energy. Chen [9] characterized the graphs with extremal ABC spectral radius for a class of given graphs. Lin et al. [10] determined the trees with the third, fourth, and fifth largest ABC spectral radii.For corona graph, Bian et al. [11] considered some Wiener-type indices of the corona graphs. Lu and Xue [12] studied the Kirchhoff index of two corona graphs. In [13], the lower and upper bounds for ABC indices of edge corona product of graphs were given. In [14], the extremal edge-version ABC index of some graph operations was given. For more information, see [15–19].Motivated by this, it is interesting to determine the extremal graphs among the setG1∘G2|G1 and G2 are connected graphs (trees)}. From Lemma 1, the problem is simple if G1 and G2 are connected graphs, so we give some conclusions directly. We mainly consider the problem for the case that G1 and G2 are trees. The main results are as follows.(1)
LetG1 and G2 be connected graphs. The ABC index of G1∘G2 attains the maximum value if and only if both G1 and G2 are complete graphs. If the ABC index of G1∘G2 attains the minimum value, then G1 and G2 must be trees.(2)
LetT1 and T2 be trees. The ABC index of T1∘T2 attains the maximum value if and only if T1 is a path and T2 is a star.


## 2. Preliminaries

The following lemmas are known somehow (for example, see [7, 8]).Lemma 2.
Letfx,y=x+y−2/xy with x,y>1. Then, fx,y strictly decreases with x for fixed y≥2, and the function ∂f/∂x increases with x. Similarly, the function fx,y strictly decreases with y for fixed x≥2, and the function ∂f/∂y increases with y.Lemma 3.
IfG is a graph with δG≥2 (δG is the minimum degree of G), then for any xy∈EG, dx+dy−2/dxdy≤2/2. Equality holds if and only if dx=2 or dy=2.Lemma 4.
Letfx,y=x+y−2/xy with x,y>1 and(4)gx,y,z=fx,y+fz,y−fx+1,y−fz−1,y.
Ifx≥z≥2, then gx,y,z<0.


## 3. The Bounds of ABC Indices ofG1∘G2

LetG1 and G2 be two simple connected graphs of orders n1 and n2, respectively, and G=G1∘G2. For a vertex v∈VG1, we use G2v to denote the copy of G2 in G which attaches to the vertex v of G1. Denote(5)E1G=EG1,E2G=∪v∈VG1vu|u∈VG2v,E3G=∪v∈VG1EG2v.Then, the following four conditions hold:(C1)VG=VG1∪∪v∈VG1VG2v.(C2)EG=E1G∪E2G∪E3G, and EkG∩ElG=ϕ for k,l=1,2,3 and k≠l.(C3) Forv∈VG1 and u∈VG2v, dGv=dG1v+n2 and dGu=dG2u+1.(C4)ABCG=ABCGE1G+ABCGE2G+ABCGE3G.From (C4) and (C3), the following theorem is obtained immediately, and we omit the proof.Theorem 1.
LetG1 and G2 be two simple connected graphs of orders n1 and n2, respectively, and G=G1∘G2. Then,(6)ABCG=∑uv∈EG1dG1u+dG1v+2n2−2dG1u+n2dG1v+n2+∑v∈VG1,u∈G2vdG1v+dG2u+n2−1dG1v+n2dG2u+1+n1∑uv∈EG2dG2u+dG2vdG2u+1dG2v+1.By Lemma1 and Theorem 1, the following results are clear.Lemma 5.
LetG1 and G2 be two simple connected graphs of orders n1≥3 and n2≥3, respectively. Then, for any edge x1x2∈EG1,(7)ABCG1∘G2>ABCG1−x1x2∘G2.Lemma 6.
LetG1 and G2 be two simple connected graphs of orders n1≥3 and n2≥3, respectively. Then, for any edge x1x2∈EG2,(8)ABCG1∘G2>ABCG1∘G2−x1x2.Theorem 2.
LetG1 and G2 be two simple connected graphs of orders n1≥3 and n2≥3, respectively. Then,(9)ABCG1∘G2≤ABCKn1∘Kn2=n1n1−122n1+n2−1−2n1+n2−1+n1n2n1+2n2−3n2n1+n2−1+n1n2n2−122n2−2n2,and the equality holds if and only if G1=Kn1 and G2=Kn2.Lemmas5 and 6 show that deleting an edge in one of the graphs (G1 and G2) will decrease the ABC index of G1∘G2. Consequently, we get the necessary condition for the ABC indices of G1∘G2 to be the minimum.Theorem 3.
If the ABC index ofG1∘G2 attains the minimum value, then G1 and G2 must be trees.


## 4. The Upper Bound of ABC Indices ofT1°T2

Since the minimal ABC trees are not unique (see [2, 5]), it seems to be difficult to characterize the corona of two trees with minimal ABC index. We leave the problem as a future task. In this section, we are going to give the upper bound of ABC indices for T1∘T2.Lemma 7.
LetT1 be any tree of order n1≥3 and T2 be a tree of order n2≥4 as depicted in Figure 2, where u1i and u2j are pendant vertices for i=1,…,s and j=1,…,t with s≥1, t≥1, u1≠u2, and dT2u2≥dT2u1. Let T3=T2−u1u1s+u2u1s. Then,(10)ABCE2T1∘T2<ABCE2T1∘T3.Figure 2
TressT2 and T3. (a) Tree T2. (b) Tree T3.
(a)(b)Proof.
DenoteT=T1∘T2, and T′=T1∘T3. Let v be any vertex of T1. We can get the result if we prove that(11)∑u∈VT2vABCTvu<∑u∈VT3vABCT′vu.
Note that both treesT2 and T3 have the same vertex set, and except u1 and u2, the other vertices have the same edges in T2 and T3. So,(12)∑u∈VT2vABCTvu−∑u∈VT3vABCT′vu=dT1v+n2+dT2u1+1−2dT1v+n2dT2u1+1+dT1v+n2+dT2u2+1−2dT1v+n2dT2u2+1−dT1v+n2+dT3u1+1−2dT1v+n2dT3u1+1−dT1v+n2+dT3u2+1−2dT1v+n2dT3u2+1.
Note thatdT3u1=dT2u1−1, dT3u2=dT2u2+1, and dT2u2≥dT2u1≥2. Then, by Lemma 4 (taking x=dT2u2+1, y=dT1v+n2, and z=dT2u1+1),(13)∑u∈VT2vABCTvu−∑u∈VT3vABCT′vu<0.
The lemma holds.
Using Lemma7 repeatedly, we can obtain the following result.Corollary 1.
LetT1 and T2 be two trees of orders n1≥3 and n2≥3, respectively. Then,(14)ABCTE2T1∘T2≤ABCT′E2T1∘Sn2,and the equality holds if and only if T2=Sn2.Theorem 4.
LetT1 and T2 be two trees of orders n1≥3 and n2≥3, respectively. Then,(15)ABCT1∘T2≤ABCT1∘Sn2,and the equality holds if and only if T2=Sn2.Proof.
DenoteT=T1∘T2 and T′=T1∘Sn2. Note ABCTE1T=ABCT′E1T′. By Corollary 1, we can get the result if we show ABCTE3T≤ABCT′E3T′.
Note that(16)ABCTE3T=∑uv∈ET2dT2u+1+dT2v+1−2dT2u+1dT2v+1,ABCT′E3T′=∑uv∈ESn2dSn2u+1+dSn2v+1−2dSn2u+1dSn2v+1=n2−112.
By Lemma3,(17)ABCTE3T≤∑uv∈ET212=n2−112=ABCT′E3T′,and equality holds if and only if dT2u+1=2 or dT2v+1=2 for each edge uv∈ET2, that is, T2=Sn2. The result follows now.Theorem 5.
LetT1 and T1′ be two trees as depicted in Figure 3, which contain T0 as a subtree, where dv=dT1v≥3, and l≥k≥1. Let n2≥4. Then,(18)ABCT1∘Sn2<ABCT1′∘Sn2.Figure 3
TreesT1 and T1′. (a) Tree T1. (b) Tree T1′.
(a)(b)Proof.
DenoteT=T1∘Sn2 and T′=T1′∘Sn2. Note that ABCTE3T=ABCT′E3T′. We can get the result if we show(19)ABCTE1T+ABCTE2T<ABCT′E1T′+ABCT′E2T′.
Firstly, we considerABCTE2T−ABCT′E2T′. Let u be any vertex of T1T1′. If w∈VSn2 is a pendant vertex of Sn2, then the ABC index of uw is 1/2. If u is a pendant vertex of T1 and T1′ and w∈VSn2 is the central vertex of Sn2, then the ABC index of uw has no change. So, we only need to calculate the ABC index of uw, where u is not a pendant vertex of T1′ and w is the central vertex of Sn2.
Denotea=n2+2, b=dv+n2, A=NT0v. Then, b>a≥6 and(20)ABCTE2T−ABCT′E2T′=dv+n2+n2−2dv+n2n2+1+n2+n2−21+n2n2−dv+n2−1+n2−2dv+n2−1n2−2+n2+n2−22+n2n2=a+b−4ba−2+2a−5a−1a−2−a+b−5b−1a−2−2a.
Combining the situation ofABCTE1T−ABCT′E1T′, we consider the following three cases.Case 1.
k=l=1.
By Lemma2,(21)ABCTE1T−ABCT′E1T′=21+n2+dv+n2−21+n2dv+n2+∑x∈Adx+n2+dv+n2−2dx+n2dv+n2−2+n2+dv+n2−1−22+n2dv+n2−1−1+n2+2+n2−21+n22+n2−∑x∈Adx+n2+dv+n2−1−2dx+n2dv+n2−1<21+n2+dv+n2−21+n2dv+n2−2+n2+dv+n2−1−22+n2dv+n2−1−1+n2+2+n2−21+n22+n2=2a+b−3ba−1−a+b−3ab−1−2a−3aa−1,ABCTE1T+ABCTE2T−ABCT′E1T′−ABCT′E2T′<2a+b−3ba−1−a+b−3ab−1−2a−3aa−1+a+b−4ba−2+2a−5a−1a−2−a+b−5b−1a−2−2a≜f1a,b.
The functionf1a,b has the following properties :(1)
The functionf1a,b is a strictly decreasing function on b for fixed a≥6.We can see the result from the graph off1a,b. For example, the graphs of f16,b and f110,b are as follows (as depicted in Figures 4 and 5).So,(22)f1a,b≤f1a,a+1=22a+1−2a−2a2−2a−3aa−1+2a−3a+1a−2+2a−5a−1a−2−22a.(2)
The maximum value of the functionf1a,a+1 is attained when a is sufficiently large.
We can get this result from the graph (as depicted in Figure6) of f1a,a+1.
Then,(23)f1a,a+1<lima⟶+∞f1a,a+1=0.
So, forb>a≥6, f1a,b<0 and the theorem follows for Case 1.Figure 4
f16,b with b>6.Figure 5
f110,b with b>10.Figure 6
f1a,a+1.Case 2.
k=1 and l≥2.
By Lemma2,(24)ABCTE1T−ABCT′E1T′=dv+n2+1+n2−2dv+n21+n2+dv+n2+2+n2−2dv+n22+n2+∑x∈Adv+n2+dx+n2−2dv+n2dx+n2−dv+n2−1+2+n2−2dv+n2−12+n2−2+n2+2+n2−22+n22+n2−∑x∈Adv+n2−1+dx+n2−2dv+n2−1dx+n2<dv+n2+1+n2−2dv+n21+n2+dv+n2+2+n2−2dv+n22+n2−dv+n2−1+2+n2−2dv+n2−12+n2−2+n2+2+n2−22+n22+n2=a+b−3ba−1+a+b−2ab−a+b−3ab−1−2a−2a2,ABCTE1T+ABCTE2T−ABCT′E1T′−ABCT′E2T′<a+b−3ba−1+a+b−2ab−a+b−3ab−1−2a−2a2+a+b−4ba−2+2a−5a−1a−2−a+b−5b−1a−2−2a≜f2a,b.
Similar to the discussions in Case1, we have that the function f2a,b is a strictly decreasing function on b for fixed a≥6, and the maximum value of the function f2a,a+1 is attained when a is sufficiently large. So,(25)f2a,b≤f2a,a+1<lima⟶+∞f2a,a+1=0.
The theorem holds for Case2.Case 3.
l≥k≥2.
By Lemma2,(26)ABCTE1T−ABCT′E1T′=2dv+n2+2+n2−2dv+n22+n2+2+n2+1+n2−22+n21+n2+∑x∈Adv+n2+dx+n2−2dv+n2dx+n2−dv+n2−1+2+n2−2dv+n2−12+n2−22+n2+2+n2−22+n22+n2−∑x∈Adv+n2−1+dx+n2−2dv+n2−1dx+n2<2dv+n2+2+n2−2dv+n22+n2+2+n2+1+n2−22+n21+n2−dv+n2−1+2+n2−2dv+n2−12+n2−22+n2+2+n2−22+n22+n2=2a+b−2ab+2a−3aa−1−a+b−3ab−1−22a−2a2,ABCTE1T+ABCTE2T−ABCT′E1T′−ABCT′E2T′<2a+b−2ab+2a−3aa−1−a+b−3ab−1−22a−2a2+a+b−4ba−2+2a−5a−1a−2−a+b−5b−1a−2−2a≜f3a,b.
Similar to the discussions in Case1, we have that the function f3a,b is a strictly decreasing function on b for fixed a≥6, and the maximum value of the function f3a,a+1 is attained when a is sufficiently large. So,(27)f3a,b≤f3a,a+1<lima⟶+∞f3a,a+1=0.
Then, the theorem holds for Case3.
By Theorems4, 5, and 1, we get the main result of this section.Theorem 6.
LetT1 and T2 be trees of orders n1≥3 and n2≥4, respectively. Then,(28)ABCT1∘T2≤ABCPn1∘Sn2=22n2+1n2+1n2+2+n1−32n2+2n2+2n2+2+22n2−1n2n2+1+n1−22n2+2+2n1n2−112,and the equality holds if and only if T1=Pn1 and T2=Sn2.The values of ABC indices ofT1°T2 for n1<3,n2<4 are as follows.Theorem 7.
LetT1 and T2 be trees of orders n1<3 and n2<4, respectively. Then,(1)
n1=1,n2=1, ABCT1∘T2=0.(2)
n1=1,n2=2, ABCT1∘T2=32/2.(3)
n1=1,n2=3, ABCT1∘T2=ABCT1∘P3=22+2/3.(4)
n1=2,n2=1, ABCT1∘T2=32/2.(5)
n1=2,n2=2, ABCT1∘T2=32+2/3.(6)
n1=2,n2=3, ABCT1∘T2=ABCP2∘P3=42+25/12+6/4.


## 5. Conclusions

In this paper, we mainly determined the upper bounds of the ABC indices ofT1∘T2. It is evident that the ABC index of G1∘G2 attains the maximum value if and only if both G1 and G2 are complete graphs. If the ABC index of G1°G2 attains the minimum value, then G1 and G2 must be trees. We deduced that the ABC index of T1∘T2 attains the maximum value if and only if T1 is a path and T2 is a star. We will discuss the minimum value of the ABC indices of the corona of two trees in near future.



---

*Source: 6699529-2021-04-02.xml*