# Unicyclic Graphs with the Fourth Extremal Wiener Indices

Authors: Guangfu Wang; Yujun Yang; Yuliang Cao; Shoujun Xu
Journal: Journal of Chemistry
 (2020)

---

## Abstract

A graph is called unicyclic if the graph contains exactly one cycle. Unicyclic graphs with the fourth extremal Wiener indices are characterized. It is shown that, among all unicyclic graphs withn≥8 vertices, C5Sn−4 and C2u1,u2S3,Sn−4 attain the fourth minimum Wiener index, whereas C3u1,u2P3,Pn−4 attains the fourth maximum Wiener index.


---

## Body

## 1. Introduction

LetG=VG,EG be a connected (molecular) graph with vertex set VG and edge set EG. For any two vertices u,v∈VG, the distance dGu,v between them is defined as the number of edges in a shortest path connecting them. The distance of a vertex u∈VG, denoted by dGu, is the sum of distances between u and all other vertices of G, i.e., dGu=∑v∈VGdGu,v. The famous Wiener index of G, denoted by WG, is defined as(1)WG=∑u,v⊆VGdGu,v=12∑u∈VGdGu.The Wiener index of a graph is a well-known topological index, and it seems that Wiener [1] was the first who considered it. Wiener himself used the name path number and conceived WG only for acyclic molecules. The definition of the Wiener index in terms of distances between vertices of a graph, such as in equation (1), was first given by Hosoya [2]. Since the middle of the 1970s, the Wiener index has been extensively studied. For research development on the Wiener index, the readers are referred to [3–7] and two special issues of MATCH [8] and Discrete Appl. Math. [9]. Analogous to the Wiener index, some other topological indices are introduced and studied (for example, see [10–13]).As summarized in [14–16], studies on the Wiener index mainly focus on trees and hexagonal systems. Recently, Wiener indices of unicyclic graphs (i.e., connected graphs containing exactly one cycle) have attracted much attention. Studies along this line include relations between Wiener and Szeged indices of unicyclic graphs [17], minimum Wiener indices of unicyclic graphs of given order, cycle length and number of penden vertices [18], minimum Wiener indices of unicyclic graphs of given matching number [19], Wiener indices of unicyclic graphs with given girth [20], minimum Wiener indices of unicyclic graphs of order n with girth g and the matching number β≥3g/2 [21], minimum Wiener indices of unicyclic graphs of order n and girth g with k pendent vertices [22], minimum Wiener index of unicyclic graphs with given bipartition [23], and so on. In [24], Tang and Deng considered unicyclic graphs with the first three smallest and largest Wiener indices. However, their characterization turned out to be incomplete and two extremal graphs were missed. Later, Nasiri et al. [25] filled the gap and presented a complete characterization to these extremal graphs. On the basis of the previous work, in this paper, we characterize unicyclic graphs with the fourth smallest and largest Wiener indices.


## 2. Notations and Lemmas

Throughout the paper, the path, star, and cycle graphs onn vertices are denoted by Pn, Sn, and Cn, respectively. Let G be a unicyclic graph of order n with its unique cycle Cm=v1v2…vmv1 of length m. Suppose that T1,T2,…,Tk 0≤k≤m are all the nontrivial components (they are all nontrivial trees) of G−ECm, and ui is the common vertex of Ti and Cm, i=1,2,…,k. Such a unicyclic graph is denoted by Cmu1,u2,…,ukT1,T2,…,Tk. Specially, G=Cn for k=0. And if k=1, we write CmT1 for Cmu1T1. Let VTi=li+1, i=1,2,…,k. Then, l=l1+l2+⋯+lk=n−m. Denote by Tn the set of all trees of order n.In the following, we summarize some known results concerning Wiener indices of unicyclic graphs which will be used in the later.Lemma 1 (see [24]).
LetG=Cmu1,u2,…,ukT1,T2,…,Tk be a unicyclic graph. Then,(2)WG=WCm+n−mω+m−1∑i=1kωi+∑i=1kWTi+∑i=1k−1∑j=i+1kliωj+liljdCmui,uj+ljωi,where ωi=dTiui, ω=dCmu, and u∈Cm.Lemma 2 (see [24]).
LetG1=Cmu1,u2,…,ukSl1+1,Sl2+1,…,Slk+1 and G2=Cmu1,u2,…,ukPl1+1,Pl2+1,…,Plk+1, where u1,u2,…,uk are the centers of Sl1+1,Sl2+1,…,Slk+1, respectively, in G1 and u1,u2,…,uk are the pendent vertices of Pl1+1,Pl2+1,…,Plk+1, respectively, in G2. Then,(3)WG1≤WG≤WG2,for any graph G=Cmu1,u2,…,ukT1,T2,…,Tk and VTi=li+1, i=1,2,…,k, with the equality on the left (or on the right) if and only if G≅G1 (or G≅G2).Lemma 3 (see [24]).
LetG1=Cmu1,u2,…,ukSl1+1,Sl2+1,…,Slk+1 and li=nTi, i=1,2,…,k. If k≥1, then(4)WG1≥WCmSl+1,with the equality if and only if G1≅CmSl+1, where l=l1+l2+⋯+lk=n−m.Lemma 4 (see [24]).
LetG2=Cmu1,u2,…,ukPl1+1,Pl2+1,…,Plk+1 and li=nTi, i=1,2,…,k. If k≥1, then(5)WG2≥WCmPl+1,with the equality if and only if G1≅CmPl+1, where l=l1+l2+⋯+lk=n−m.Lemma 5 (see [25]).
Ifn≥8 and m≥3, then WCmSn−m+1−WCm−1Sn−m+2>0.
Besides, we also need the following result.Lemma 6 (see [22]).
Let H,X, and Y be three connected pairwise vertex-set disjoint graphs. Suppose that u and v are the two vertices of H, v′ is a vertex of X, and u′ is a vertex of Y. Let G be the graph obtained from H,X,andY by identifying v with v′ and u with u′, respectively. Let G1∗ be the graph obtained from H,X,andY by identifying vertices v,v′,andu′, and let G2∗ be the graph obtained from H,X,andY by identifying vertices u,v′,u′. Then,(6)WG1∗<WGorWG2∗<WG.


## 3. Results

### 3.1. Unicyclic Graphs with the Fourth Minimum Wiener Index

LetC3Tn−5,11 be the unicyclic graph as shown in Figure 1(a). Then, unicyclic graphs with the first smallest Wiener indices are completely characterized in the following result.Figure 1
Unicyclic graphsC3Tn−5,11 (a) and C3Tn−6,21 (b).
(a)
(b)Theorem 1 (see [25]).
SupposeG=Cmu1,u2,…,ukT1,T2,…,Tk is a unicyclic graph of order n, with n≥7. If G≇Sn+e,C4Sn−3,C3u1,u2S2,Sn−3, then(7)WSn+e<WC4Sn−3=WC3u1,u2S2,Sn−3<WC3Tn−5,11≤WG,with equality if and only if(8)G≅C3Tn−5,11,ifn>7,C3u1,u2S3,S3orC5S3,ifn=7.
As illustrated in the following theorem, we show thatC5Sn−4 and C3u1,u2S3,Sn−4 have the fourth smallest Wiener indices.Theorem 2.
SupposeG=Cmu1,u2,…,ukT1,T2,…,Tk is a unicyclic graph of order n, with n≥8. If G≇Sn+e,C4Sn−3,C3u1,u2S2,Sn−3,C3Tn−5,11, then(9)WSn+e<WC4Sn−3=WC3u1,u2S2,Sn−3<WC3Tn−5,11<WC5Sn−4=WC3u1,u2S3,Sn−4≤WG,with equality if and only if G≅C5Sn−4 or C3u1,u2S3,Sn−4.Proof.
By Lemma1,(10)WSn+e<WC4Sn−3=WC3u1,u2S2,Sn−3<WC3Tn−5,11=n2−n−3.
On the other hand, by Lemma1, it is easily computed that(11)WC5Sn−4=WC3u1,u2S3,Sn−4=n2−10.
Hence, forn≥8, WSn+e<WC4Sn−3=WC3u1,u2S2,Sn−3<WC3Tn−5,11<WC5Sn−4=WC3u1,u2S3,Sn−4. So, it suffices to show that if G is a n-vertex unicyclic graph (n≥8), such that G≇Sn+e,C4Sn−3,C3u1,u2S2,Sn−3,C3Tn−5,11, then WC5Sn−4≤WG, with equality if and only if G≅C5Sn−4 or C3u1,u2S3,Sn−4. To this end, for convenience, we distinguish three cases that m=3,4 or m≥5.Case 1 (m≥5).
Ifk=0, then G=Cn. It is well known that(12)WCn=18n3,ifnis even,18nn2−1,otherwise.
Hence, ifn is even, then(13)WG−WC5Sn−4=18n3−n2−10=18n3−n2+10>0,and if n is odd, then(14)WG−WC5Sn−4=18nn2−1−n2−10=18n3−98n2+10>0,as desired.
Now assume thatk≥1. Then, by Lemmas 2, 3, and 5,(15)WG≥WCmu1,u2,…,ukSl1+1,Sl2+1,…,Slk+1≥WCmSn−m+1≥WC5Sn−4,with equality if and only if G≅C5Sn−4.Case 2 (m=4).
In this case, we consider four subcases thatk=1,2,3, or 4.Subcase 1 (k=1).
In this case,G=C4T1. Since G=C4T1≇C4Sn−3, it has been shown in [25] that(16)WG≥WC4Tn−6,11=n2−7.
Hence,WG≥WC4Tn−6,11=n2−7>n2−10=WC5Sn−4, as desired.Subcase 2 (k=2).
In this case,G=C4u1,u2T1,T2. It has been shown in [24] that(17)WG=WC4u1,u2T1,T2≥WC4u1,u2Sl1+1,Sl2+1=n2−n−4+αl1l2,where α=1 if u1 and u2 are adjacent in C4; otherwise, α=2. Noticing that l1+l2=n−4, we have(18)WG−WC5Sn−4≥n2−n−4+αl1l2−n2−10=αl1l2−n+6≥1×n−5−n+6>0.Subcase 3 (k=3).
In this case,G=C4u1,u2,u3T1,T2,T3. Let G1∗ be the graph obtained from G by first removing T1 from G and then identifying the root of T1 with u2, and let G2∗ be the graph obtained from G by first removing T2 from G and then identifying the root of T2 with u1. Then, by Lemma 6, WG1∗<WG or WG2∗<WG. Suppose that WG1∗<WG. Then, according to the proof of Subcase 2, we know that WG1∗>WC5Sn−4. Hence, we have WG>WC5Sn−4, as desired.Subcase 4 (k=4).
The same argument as Subcase 3 shows that(19)WG=WC4u1,u2,u3,u4T1,T2,T3,T4>WC5Sn−4.Case 3 (m=3).
For convenience, we distinguish the following three cases.Subcase 5 (k=1).
In this case,G=C3T1. Let C3Tn−6,12 be the graph shown in Figure 1(b) . Then, it is well known that Sn−3, Tn−5,11, and Tn−6,12 has the minimum, second minimum, and third minimum of Wiener index in Tn−2. Since G≇Sn+e,C3Tn−5,11, we know T1≇Sn−2,Tn−5,11. By Lemma 1,(20)WG=WC3T1=WC3+n−3duC3+3du1T1+WT1.
Noticing thatWT1≥WTn−6,12 and du1T1≥du1Tn−6,12, we readily have(21)WG≥WC3Tn−6,12=n2−8>WC5Sn−4.Subcase 6 (k=2).
In this case,G=C3u1,u2T1,T2. Without loss of generality, we assume that l1≤l2. Now, we consider the following two cases:(1)
l1=1. In this case, T1≅S2. By Lemma 1,(22)WG=WC3u1,u2S2,T2=WC3+n−3ω+m−1du1S2+du2T2+WS2+WT2+l1du2T2+l1l2dC3u1,u2+l2du1S2.SinceG≇C3u1,u2S2,Sn−3, we have T2≇Sn−3. So WT2≥WTn−6,11 and du2T2≥du2Tn−6,11. It thus follows that(23)WG=WC3u1,u2S2,T2≥WC3u1,u2S2,Tn−6,11.Again By Lemma1, simple computation shows that WC3u1,u2S2,Tn−6,11=n2−7. Hence, we have WG≥WC3u1,u2S2,Tn−6,11=n2−7>n2−10=WC5Sn−4.(2)
l1≥2. In this case, it is obvious that G≇C3u1,u2S2,Sn−3. By Lemma 2,(24)WG=WC3u1,u2T1,T2≥WC3u1,u2Sl1+1,Sl2+1.
It has been computed in [24] that(25)WC3u1,u2Sl1+1,Sl2+1=n2−2n+l1l2.
Bearing in mind thatl1≥2 and l1+l2=n−3, we readily have(26)WC3u1,u2Sl1+1,Sl2+1=n2−2n+l1l2≥n2−2n+2n−5=n2−10,with equality if and only if l1=2 and l2=n−5. Hence,(27)WG=WC3u1,u2T1,T2≥WC3u1,u2Sl1+1,Sl2+1≥WC3u1,u2S3,Sn−4=n2−10,with equality if and only if G≅C3u1,u2S3,Sn−4.Subcase 7 (k=3).
In this case,G=C3u1,u2,u3T1,T2,T3. It has been shown in [24] that(28)WG≥WC3u1,u2,u3Sl1+1,Sl2+1,Sl3+1=n2−2n+l1l2+l1l3+l2l3.
Sincel1+l2+l3=n−3, we have(29)l1l2+l1l3+l2l3=l1l2+l1+l2l3=l1l2+l1+l2n−3−l1+l2.
Ifl1+l2=n−4, then l1l2≥n−5 and thus l1l2+l1l3+l2l3≥n−5+n−4n−3−n−4=2n−9; otherwise, 2≤l1+l2≤n−5, then l1l2≥1 and thus l1l2+l1l3+l2l3≥1+n−5n−3−n−5=2n−9. Hence, in both cases, we have l1l2+l1l3+l2l3≥2n−9 and consequently,(30)WG≥WC3u1,u2,u3Sl1+1,Sl2+1,Sl3+1≥n2−2n+2n−9=n2−9>n2−10.


### 3.2. Unicyclic Graphs with the Fourth Maximum Wiener Index

Unicyclic graphs with the first three largest Wiener indices were first characterized by Tang and Deng [24], but one extremal graph was missed. Then, Nasiri et al. [25] gave a complete characterization.Theorem 3 (see [25]).
SupposeG=Cmu1,u2,…,ukT1,T2,…,Tk is a unicyclic graph of order n, with n≥6. If G≇C3Pn−2,C4Pn−3,andC3u1,u2P2,Pn−3, then(31)WG≤WC3Tn−5,1,1<WC4Pn−3=WC3u1,u2P2,Pn−3<WC3Pn−2,with equality if and only if G=C3Tn−5,1,1. Here, Tn−5,1,1 is a unicyclic graph depicted in Figure 2(a).
Now, we characterize unicyclic graphs with the fourth largest Wiener indices.Figure 2
Unicyclic graphsC3Tn−5,1,1 (a) and C3Tn−6,1,2 (b).
(a)
(b)Theorem 4.
Suppose thatG=Cmu1,u2,…,ukT1,T2,…,Tk is a unicyclic graph of order n, with n≥8. If G≇C3Pn−2,C4Pn−3,C3u1,u2P2,Pn−3,andC3Tn−5,1,1, then(32)WG≤WC3u1,u2P3,Pn−4<WC3Tn−5,1,1<WC4Pn−3=WC3u1,u2P2,Pn−3<WC3Pn−2,with equality if and only if G=C3u1,u2P3,Pn−4.Proof.
By Lemma1, it is easily computed that for n≥8,(33)16n3−19n+72=WC3u1,u2P3,Pn−4<16n3−13n+30=WC3Tn−5,1,1.
Hence, according to Theorem4, we only need to show that for n≥8, if G≇C3Pn−2,C4Pn−3,C3u1,u2P2,Pn−3,andC3Tn−5,1,1, then WG≤WC3u1,u2P3,Pn−4, with equality if and only if G≅C3u1,u2P3,Pn−4. To prove our result, we distinguish the following three cases according to m.Case 4 (m≥5).
In this case, we consider two subcases thatk=0 and k≥1.Subcase 8 (k=0).
In this caseG≅Cn. If n is even, then(34)WCn−WC3u1,u2P3,Pn−4=18n3−16n3−19n+72=−124n3+196n−12<0.
Ifn is odd, then(35)WCn−WC3u1,u2P3,Pn−4=18nn2−1−16n3−19n+72=−124n3+7324n−12<0.
Hence,WG<WC3u1,u2P3,Pn−4 as desired.Subcase 9 (k≥1).
By Lemmas2 and 4,(36)WG≤WCmu1,u2,…,ukPl1+1,Pl2+1,…,Plk+1≤WCmPl+1.
We now prove thatWCmPl+1<WC3u1,u2P3,Pn−4. We first assume that m is even. Then, m≥6 and by Lemma 1,(37)WCmPl+1=16n3+−32m2+3m−1n+54m3−3m2+m.
Thus,(38)WC3u1,u2P3,Pn−4−WCmPl+1=16n3−19n+72−16n3+−32m2+3m−1n+54m3−3m2+m=14m2−2m−12n−1245m3−12m2+4m−288≥14m2−2m−12m−1245m3−12m2+4m−288=124m3−196m+12>0.
Now assume thatm is odd. Then, m≥5 and by Lemma 1(39)WCmPl+1=16n3+−32m2+3m−1n+54m3−3m2+m−14n+18m.
Thus,(40)WC3u1,u2P3,Pn−4−WCmPl+1=16n3−19n+72−16n3+−32m2+3m−1n+54m3−3m2+m+14n−18m=14m2−2m−11n−1245m3−12m2+7m−288≥14m2−2m−11m−1245m3−12m2+7m−288=124m3−7324m+12>0.
Therefore, we could conclude thatWCmPl+1<WC3u1,u2P3,Pn−4.Case 5 (m=4).
We consider subcases thatk=1,2,3, or 4.Subcase 10 (k=1).
In this case,G=C4T1 with T1 being a tree of order n−3. By assumption, G≇C4Pn−3 and so T1≇Pn−3. By Lemma 1,(41)WG=WC4T1=WC4+n−3ω+3du1T1+WT1.
Noticing thatTn−6,1,1 has the second maximum Wiener index in Tn−3 and dT1u1≤dTn−6,1,1u1, we have(42)WG=WC4T1≤WC4Tn−6,1,1=16n3−19n+54.
Thus, we have(43)WG≤16n3−19n+54<16n3−19n+72=WC3u1,u2P3,Pn−4,as desired.Subcase 11 (k=2).
By Lemma2, we have(44)WG=WC4u1,u2T1,T2≤WC4u1,u2Pl1+1,Pl2+1.
In addition, it has been shown in [24] that(45)WC3u1,u2P3,Pn−4−WC4u1,u2Pl1+1,Pl2+1=3−αl1l2−n+6,where α=1 if u1 and u2 are adjacent and 2, otherwise. Bearing in mind that l1+l2=n−4, l1l2≥n−5 and(46)WC3u1,u2P3,Pn−4−WC4u1,u2Pl1+1,Pl2+1>3−2n−5−n+6=1>0.
So we haveWC3u1,u2P3,Pn−4−WG>0 as desired.Subcase 12 (k=3 or k=4).
In this case, it has been shown in [24] that(47)WC4u1,u2,u3T1,T2,T3≤WC4u1,u2,u3Pl1+1,Pl2+1,Pl3+1<WC4Tn−6,1,1,WC4u1,u2,u3,u4T1,T2,T3,T4≤WC4u1,u2,u3,u4Pl1+1,Pl2+1,Pl3+1,Pl4+1<WC4Tn−6,1,1.
As shown in Subcase 10,WC4Tn−6,1,1<WC3u1,u2P3,Pn−4. Thus, it is done.Case 6 (m=3).
We distinguish three cases according tok=1,2, or 3.Subcase 13 (k=1).
In this case,G=C3T1. By assumption, C3T1≇C3Pn−2,C3Tn−5,1,1 and so T1≇Pn−2,Tn−5,1,1. By Lemma 1,(48)WC3T1=WC3+WT1+2n−3+2dT1u1.
SinceTn−6,1,2 has the third maximum Wiener index in Tn−2 and T1≇Pn−2,Tn−5,1,1, we readily have WC3T1≤WC3Tn−6,1,2. It is easily verified that(49)WC3Tn−6,1,2=16n3−19n+48<WC3u1,u2P3,Pn−4,as desired.Subcase 14 (k=2).
In this case,G=C3u1,u2T1,T2. Without loss of generality, we suppose that l1≤l2. For convenience, we distinguish the following two cases:(1)
l1=1; that is, T1≅P2. Since G≇C3P2,Pn−3, T2≇Pn−3. It is easy to compute that(50)WC3P2,T2=WC3P2+WT2+3dT2u2+2n−4.SinceTn−6,1,1 has the second maximum Wiener index in Tn−3 and T2≇Pn−3, we have(51)WC3P2,T2≤WC3P2,Tn−6,1,1=16n3−19n+54.Noticing thatWC3P2,Tn−6,1,1<WC3u1,u2P3,Pn−4, we complete the proof.(2)
l1≥2. In this case, we have(52)WG=WC3u1,u2T1,T2≤WC3u1,u2Pl1+1,Pl2+1.
By Lemma1, simple calculation shows that(53)WC3u1,u2Pl1+1,Pl2+1=16n3−76n−l1l2+2.
On the other hand,(54)WC3u1,u2Pl1+1,Pl2+1−WC3u1,u2P3,Pn−4=16n3−76n−l1l2+2−16n3−19n+72=2n−10−l1l2≤2n−10−2n−5=0,with equality if and only if l1=2 (and thus, l2=n−5), that is, if and only if C3u1,u2Pl1+1,Pl2+1≅C3u1,u2P3,Pn−4. Hence, WG=WC3u1,u2T1,T2≤WC3u1,u2P3,Pn−4, with equality if and only if G≅C3u1,u2P3,Pn−4.Subcase 15 (k=3).
By Lemma2, we have(55)WG=WC3u1,u2,u3T1,T2,T3≤WC3u1,u2,u3Pl1+1,Pl2+1,Pl3+1.
It has been shown in [25] that(56)WC3u1,u2,u3Pl1+1,Pl2+1,Pl3+1=16n3−76n+2−l1l2l3+l1l2+l1l3+l2l3.
Hence,(57)WC3u1,u2,u3Pl1+1,Pl2+1,Pl3+1−WC3u1,u2P3,Pn−4=16n3−76n+2−l1l2l3+l1l2+l1l3+l2l3−16n3−19n+72=2n−10−l1l2l3+l1l2+l1l3+l2l3.
Since it has been shown in the proof of Theorem2 that l1l2+l1l3+l2l3≥2n−9, it immediately follows that(58)WC3u1,u2,u3Pl1+1,Pl2+1,Pl3+1−WC3u1,u2P3,Pn−4<0,and the proof is complete.


## 3.1. Unicyclic Graphs with the Fourth Minimum Wiener Index

LetC3Tn−5,11 be the unicyclic graph as shown in Figure 1(a). Then, unicyclic graphs with the first smallest Wiener indices are completely characterized in the following result.Figure 1
Unicyclic graphsC3Tn−5,11 (a) and C3Tn−6,21 (b).
(a)
(b)Theorem 1 (see [25]).
SupposeG=Cmu1,u2,…,ukT1,T2,…,Tk is a unicyclic graph of order n, with n≥7. If G≇Sn+e,C4Sn−3,C3u1,u2S2,Sn−3, then(7)WSn+e<WC4Sn−3=WC3u1,u2S2,Sn−3<WC3Tn−5,11≤WG,with equality if and only if(8)G≅C3Tn−5,11,ifn>7,C3u1,u2S3,S3orC5S3,ifn=7.
As illustrated in the following theorem, we show thatC5Sn−4 and C3u1,u2S3,Sn−4 have the fourth smallest Wiener indices.Theorem 2.
SupposeG=Cmu1,u2,…,ukT1,T2,…,Tk is a unicyclic graph of order n, with n≥8. If G≇Sn+e,C4Sn−3,C3u1,u2S2,Sn−3,C3Tn−5,11, then(9)WSn+e<WC4Sn−3=WC3u1,u2S2,Sn−3<WC3Tn−5,11<WC5Sn−4=WC3u1,u2S3,Sn−4≤WG,with equality if and only if G≅C5Sn−4 or C3u1,u2S3,Sn−4.Proof.
By Lemma1,(10)WSn+e<WC4Sn−3=WC3u1,u2S2,Sn−3<WC3Tn−5,11=n2−n−3.
On the other hand, by Lemma1, it is easily computed that(11)WC5Sn−4=WC3u1,u2S3,Sn−4=n2−10.
Hence, forn≥8, WSn+e<WC4Sn−3=WC3u1,u2S2,Sn−3<WC3Tn−5,11<WC5Sn−4=WC3u1,u2S3,Sn−4. So, it suffices to show that if G is a n-vertex unicyclic graph (n≥8), such that G≇Sn+e,C4Sn−3,C3u1,u2S2,Sn−3,C3Tn−5,11, then WC5Sn−4≤WG, with equality if and only if G≅C5Sn−4 or C3u1,u2S3,Sn−4. To this end, for convenience, we distinguish three cases that m=3,4 or m≥5.Case 1 (m≥5).
Ifk=0, then G=Cn. It is well known that(12)WCn=18n3,ifnis even,18nn2−1,otherwise.
Hence, ifn is even, then(13)WG−WC5Sn−4=18n3−n2−10=18n3−n2+10>0,and if n is odd, then(14)WG−WC5Sn−4=18nn2−1−n2−10=18n3−98n2+10>0,as desired.
Now assume thatk≥1. Then, by Lemmas 2, 3, and 5,(15)WG≥WCmu1,u2,…,ukSl1+1,Sl2+1,…,Slk+1≥WCmSn−m+1≥WC5Sn−4,with equality if and only if G≅C5Sn−4.Case 2 (m=4).
In this case, we consider four subcases thatk=1,2,3, or 4.Subcase 1 (k=1).
In this case,G=C4T1. Since G=C4T1≇C4Sn−3, it has been shown in [25] that(16)WG≥WC4Tn−6,11=n2−7.
Hence,WG≥WC4Tn−6,11=n2−7>n2−10=WC5Sn−4, as desired.Subcase 2 (k=2).
In this case,G=C4u1,u2T1,T2. It has been shown in [24] that(17)WG=WC4u1,u2T1,T2≥WC4u1,u2Sl1+1,Sl2+1=n2−n−4+αl1l2,where α=1 if u1 and u2 are adjacent in C4; otherwise, α=2. Noticing that l1+l2=n−4, we have(18)WG−WC5Sn−4≥n2−n−4+αl1l2−n2−10=αl1l2−n+6≥1×n−5−n+6>0.Subcase 3 (k=3).
In this case,G=C4u1,u2,u3T1,T2,T3. Let G1∗ be the graph obtained from G by first removing T1 from G and then identifying the root of T1 with u2, and let G2∗ be the graph obtained from G by first removing T2 from G and then identifying the root of T2 with u1. Then, by Lemma 6, WG1∗<WG or WG2∗<WG. Suppose that WG1∗<WG. Then, according to the proof of Subcase 2, we know that WG1∗>WC5Sn−4. Hence, we have WG>WC5Sn−4, as desired.Subcase 4 (k=4).
The same argument as Subcase 3 shows that(19)WG=WC4u1,u2,u3,u4T1,T2,T3,T4>WC5Sn−4.Case 3 (m=3).
For convenience, we distinguish the following three cases.Subcase 5 (k=1).
In this case,G=C3T1. Let C3Tn−6,12 be the graph shown in Figure 1(b) . Then, it is well known that Sn−3, Tn−5,11, and Tn−6,12 has the minimum, second minimum, and third minimum of Wiener index in Tn−2. Since G≇Sn+e,C3Tn−5,11, we know T1≇Sn−2,Tn−5,11. By Lemma 1,(20)WG=WC3T1=WC3+n−3duC3+3du1T1+WT1.
Noticing thatWT1≥WTn−6,12 and du1T1≥du1Tn−6,12, we readily have(21)WG≥WC3Tn−6,12=n2−8>WC5Sn−4.Subcase 6 (k=2).
In this case,G=C3u1,u2T1,T2. Without loss of generality, we assume that l1≤l2. Now, we consider the following two cases:(1)
l1=1. In this case, T1≅S2. By Lemma 1,(22)WG=WC3u1,u2S2,T2=WC3+n−3ω+m−1du1S2+du2T2+WS2+WT2+l1du2T2+l1l2dC3u1,u2+l2du1S2.SinceG≇C3u1,u2S2,Sn−3, we have T2≇Sn−3. So WT2≥WTn−6,11 and du2T2≥du2Tn−6,11. It thus follows that(23)WG=WC3u1,u2S2,T2≥WC3u1,u2S2,Tn−6,11.Again By Lemma1, simple computation shows that WC3u1,u2S2,Tn−6,11=n2−7. Hence, we have WG≥WC3u1,u2S2,Tn−6,11=n2−7>n2−10=WC5Sn−4.(2)
l1≥2. In this case, it is obvious that G≇C3u1,u2S2,Sn−3. By Lemma 2,(24)WG=WC3u1,u2T1,T2≥WC3u1,u2Sl1+1,Sl2+1.
It has been computed in [24] that(25)WC3u1,u2Sl1+1,Sl2+1=n2−2n+l1l2.
Bearing in mind thatl1≥2 and l1+l2=n−3, we readily have(26)WC3u1,u2Sl1+1,Sl2+1=n2−2n+l1l2≥n2−2n+2n−5=n2−10,with equality if and only if l1=2 and l2=n−5. Hence,(27)WG=WC3u1,u2T1,T2≥WC3u1,u2Sl1+1,Sl2+1≥WC3u1,u2S3,Sn−4=n2−10,with equality if and only if G≅C3u1,u2S3,Sn−4.Subcase 7 (k=3).
In this case,G=C3u1,u2,u3T1,T2,T3. It has been shown in [24] that(28)WG≥WC3u1,u2,u3Sl1+1,Sl2+1,Sl3+1=n2−2n+l1l2+l1l3+l2l3.
Sincel1+l2+l3=n−3, we have(29)l1l2+l1l3+l2l3=l1l2+l1+l2l3=l1l2+l1+l2n−3−l1+l2.
Ifl1+l2=n−4, then l1l2≥n−5 and thus l1l2+l1l3+l2l3≥n−5+n−4n−3−n−4=2n−9; otherwise, 2≤l1+l2≤n−5, then l1l2≥1 and thus l1l2+l1l3+l2l3≥1+n−5n−3−n−5=2n−9. Hence, in both cases, we have l1l2+l1l3+l2l3≥2n−9 and consequently,(30)WG≥WC3u1,u2,u3Sl1+1,Sl2+1,Sl3+1≥n2−2n+2n−9=n2−9>n2−10.


## 3.2. Unicyclic Graphs with the Fourth Maximum Wiener Index

Unicyclic graphs with the first three largest Wiener indices were first characterized by Tang and Deng [24], but one extremal graph was missed. Then, Nasiri et al. [25] gave a complete characterization.Theorem 3 (see [25]).
SupposeG=Cmu1,u2,…,ukT1,T2,…,Tk is a unicyclic graph of order n, with n≥6. If G≇C3Pn−2,C4Pn−3,andC3u1,u2P2,Pn−3, then(31)WG≤WC3Tn−5,1,1<WC4Pn−3=WC3u1,u2P2,Pn−3<WC3Pn−2,with equality if and only if G=C3Tn−5,1,1. Here, Tn−5,1,1 is a unicyclic graph depicted in Figure 2(a).
Now, we characterize unicyclic graphs with the fourth largest Wiener indices.Figure 2
Unicyclic graphsC3Tn−5,1,1 (a) and C3Tn−6,1,2 (b).
(a)
(b)Theorem 4.
Suppose thatG=Cmu1,u2,…,ukT1,T2,…,Tk is a unicyclic graph of order n, with n≥8. If G≇C3Pn−2,C4Pn−3,C3u1,u2P2,Pn−3,andC3Tn−5,1,1, then(32)WG≤WC3u1,u2P3,Pn−4<WC3Tn−5,1,1<WC4Pn−3=WC3u1,u2P2,Pn−3<WC3Pn−2,with equality if and only if G=C3u1,u2P3,Pn−4.Proof.
By Lemma1, it is easily computed that for n≥8,(33)16n3−19n+72=WC3u1,u2P3,Pn−4<16n3−13n+30=WC3Tn−5,1,1.
Hence, according to Theorem4, we only need to show that for n≥8, if G≇C3Pn−2,C4Pn−3,C3u1,u2P2,Pn−3,andC3Tn−5,1,1, then WG≤WC3u1,u2P3,Pn−4, with equality if and only if G≅C3u1,u2P3,Pn−4. To prove our result, we distinguish the following three cases according to m.Case 4 (m≥5).
In this case, we consider two subcases thatk=0 and k≥1.Subcase 8 (k=0).
In this caseG≅Cn. If n is even, then(34)WCn−WC3u1,u2P3,Pn−4=18n3−16n3−19n+72=−124n3+196n−12<0.
Ifn is odd, then(35)WCn−WC3u1,u2P3,Pn−4=18nn2−1−16n3−19n+72=−124n3+7324n−12<0.
Hence,WG<WC3u1,u2P3,Pn−4 as desired.Subcase 9 (k≥1).
By Lemmas2 and 4,(36)WG≤WCmu1,u2,…,ukPl1+1,Pl2+1,…,Plk+1≤WCmPl+1.
We now prove thatWCmPl+1<WC3u1,u2P3,Pn−4. We first assume that m is even. Then, m≥6 and by Lemma 1,(37)WCmPl+1=16n3+−32m2+3m−1n+54m3−3m2+m.
Thus,(38)WC3u1,u2P3,Pn−4−WCmPl+1=16n3−19n+72−16n3+−32m2+3m−1n+54m3−3m2+m=14m2−2m−12n−1245m3−12m2+4m−288≥14m2−2m−12m−1245m3−12m2+4m−288=124m3−196m+12>0.
Now assume thatm is odd. Then, m≥5 and by Lemma 1(39)WCmPl+1=16n3+−32m2+3m−1n+54m3−3m2+m−14n+18m.
Thus,(40)WC3u1,u2P3,Pn−4−WCmPl+1=16n3−19n+72−16n3+−32m2+3m−1n+54m3−3m2+m+14n−18m=14m2−2m−11n−1245m3−12m2+7m−288≥14m2−2m−11m−1245m3−12m2+7m−288=124m3−7324m+12>0.
Therefore, we could conclude thatWCmPl+1<WC3u1,u2P3,Pn−4.Case 5 (m=4).
We consider subcases thatk=1,2,3, or 4.Subcase 10 (k=1).
In this case,G=C4T1 with T1 being a tree of order n−3. By assumption, G≇C4Pn−3 and so T1≇Pn−3. By Lemma 1,(41)WG=WC4T1=WC4+n−3ω+3du1T1+WT1.
Noticing thatTn−6,1,1 has the second maximum Wiener index in Tn−3 and dT1u1≤dTn−6,1,1u1, we have(42)WG=WC4T1≤WC4Tn−6,1,1=16n3−19n+54.
Thus, we have(43)WG≤16n3−19n+54<16n3−19n+72=WC3u1,u2P3,Pn−4,as desired.Subcase 11 (k=2).
By Lemma2, we have(44)WG=WC4u1,u2T1,T2≤WC4u1,u2Pl1+1,Pl2+1.
In addition, it has been shown in [24] that(45)WC3u1,u2P3,Pn−4−WC4u1,u2Pl1+1,Pl2+1=3−αl1l2−n+6,where α=1 if u1 and u2 are adjacent and 2, otherwise. Bearing in mind that l1+l2=n−4, l1l2≥n−5 and(46)WC3u1,u2P3,Pn−4−WC4u1,u2Pl1+1,Pl2+1>3−2n−5−n+6=1>0.
So we haveWC3u1,u2P3,Pn−4−WG>0 as desired.Subcase 12 (k=3 or k=4).
In this case, it has been shown in [24] that(47)WC4u1,u2,u3T1,T2,T3≤WC4u1,u2,u3Pl1+1,Pl2+1,Pl3+1<WC4Tn−6,1,1,WC4u1,u2,u3,u4T1,T2,T3,T4≤WC4u1,u2,u3,u4Pl1+1,Pl2+1,Pl3+1,Pl4+1<WC4Tn−6,1,1.
As shown in Subcase 10,WC4Tn−6,1,1<WC3u1,u2P3,Pn−4. Thus, it is done.Case 6 (m=3).
We distinguish three cases according tok=1,2, or 3.Subcase 13 (k=1).
In this case,G=C3T1. By assumption, C3T1≇C3Pn−2,C3Tn−5,1,1 and so T1≇Pn−2,Tn−5,1,1. By Lemma 1,(48)WC3T1=WC3+WT1+2n−3+2dT1u1.
SinceTn−6,1,2 has the third maximum Wiener index in Tn−2 and T1≇Pn−2,Tn−5,1,1, we readily have WC3T1≤WC3Tn−6,1,2. It is easily verified that(49)WC3Tn−6,1,2=16n3−19n+48<WC3u1,u2P3,Pn−4,as desired.Subcase 14 (k=2).
In this case,G=C3u1,u2T1,T2. Without loss of generality, we suppose that l1≤l2. For convenience, we distinguish the following two cases:(1)
l1=1; that is, T1≅P2. Since G≇C3P2,Pn−3, T2≇Pn−3. It is easy to compute that(50)WC3P2,T2=WC3P2+WT2+3dT2u2+2n−4.SinceTn−6,1,1 has the second maximum Wiener index in Tn−3 and T2≇Pn−3, we have(51)WC3P2,T2≤WC3P2,Tn−6,1,1=16n3−19n+54.Noticing thatWC3P2,Tn−6,1,1<WC3u1,u2P3,Pn−4, we complete the proof.(2)
l1≥2. In this case, we have(52)WG=WC3u1,u2T1,T2≤WC3u1,u2Pl1+1,Pl2+1.
By Lemma1, simple calculation shows that(53)WC3u1,u2Pl1+1,Pl2+1=16n3−76n−l1l2+2.
On the other hand,(54)WC3u1,u2Pl1+1,Pl2+1−WC3u1,u2P3,Pn−4=16n3−76n−l1l2+2−16n3−19n+72=2n−10−l1l2≤2n−10−2n−5=0,with equality if and only if l1=2 (and thus, l2=n−5), that is, if and only if C3u1,u2Pl1+1,Pl2+1≅C3u1,u2P3,Pn−4. Hence, WG=WC3u1,u2T1,T2≤WC3u1,u2P3,Pn−4, with equality if and only if G≅C3u1,u2P3,Pn−4.Subcase 15 (k=3).
By Lemma2, we have(55)WG=WC3u1,u2,u3T1,T2,T3≤WC3u1,u2,u3Pl1+1,Pl2+1,Pl3+1.
It has been shown in [25] that(56)WC3u1,u2,u3Pl1+1,Pl2+1,Pl3+1=16n3−76n+2−l1l2l3+l1l2+l1l3+l2l3.
Hence,(57)WC3u1,u2,u3Pl1+1,Pl2+1,Pl3+1−WC3u1,u2P3,Pn−4=16n3−76n+2−l1l2l3+l1l2+l1l3+l2l3−16n3−19n+72=2n−10−l1l2l3+l1l2+l1l3+l2l3.
Since it has been shown in the proof of Theorem2 that l1l2+l1l3+l2l3≥2n−9, it immediately follows that(58)WC3u1,u2,u3Pl1+1,Pl2+1,Pl3+1−WC3u1,u2P3,Pn−4<0,and the proof is complete.



---

*Source: 2878901-2020-04-15.xml*