# On Mostar and Edge Mostar Indices of Graphs

Authors: Ali Ghalavand; Ali Reza Ashrafi; Mardjan Hakimi-Nezhaad
Journal: Journal of Mathematics
 (2021)

---

## Abstract

LetG be a graph with edge set EG and e=uv∈EG. Define nue,G and mue,G to be the number of vertices of G closer to u than to v and the number of edges of G closer to u than to v, respectively. The numbers nve,G and mve,G can be defined in an analogous way. The Mostar and edge Mostar indices of G are new graph invariants defined as MoG=∑uv∈EGnuuv,G−nvuv,G and MoeG=∑uv∈EGmuuv,G−mvuv,G, respectively. In this paper, an upper bound for the Mostar and edge Mostar indices of a tree in terms of its diameter is given. Next, the trees with the smallest and the largest Mostar and edge Mostar indices are also given. Finally, a recent conjecture of Liu, Song, Xiao, and Tang (2020) on bicyclic graphs with a given order, for which extremal values of the edge Mostar index are attained, will be proved. In addition, some new open questions are presented.


---

## Body

## 1. Introduction

In this paper, graph means undirected and connected finite graph without loops or multiple edges. The vertex and edge sets of such a graphG will be denoted by V=VG and E=EG, respectively. We use the notations degGv and Nv,G for the degree of a vertex v and the set of all vertices adjacent to v, respectively. Suppose e is an edge and xandy are two nonadjacent vertices of G. Then, G−e is the subgraph of G obtained by deleting the edge e and G+xy is a graph obtained from G by adding an edge connecting x and y.IfH and G are graphs such that VH⊆VG and EH⊆EG, then we call H to be a subgraph of G. The subgraph P with vertex set v0,v1,…,vr and edge set v0v1,v1v2,…,vr−1vr is called a pendent path of G if degGv0≥3, degGvr=1 and degGv1=degGv2=⋯=degGvr−1=2, when r≥2. While, a subgraph Q with vertex set u0,u1,…,us and edge set u0u1,u1u2,…,us−1us is called an internal path if degGv0,degGvs≥3 and degGv1=degGv2=⋯=degGvs−1=2, when s≥2. An edge incident to a pendent vertex is called a pendent edge.SupposeG is a connected graph with two vertices u and v. The distance dGu,v is defined as the number of edges in a shortest path connecting u and v. The cyclomatic number of G, γG, is defined to be γG=EG−VG + 1. If γG=0,1,2,3,4,5, then the graph G is said to be tree, unicyclic, bicyclic, tricyclic, tetracyclic, and pentacyclic, respectively. We refer the readers to consult the famous book of West [1] for our graph theory notions and notations.In a recent paper, Dosˇlic´ et al. [2] introduced a new bond-additive structural invariant as a quantitative refinement of the distance nonbalancedness and also a measure of peripherality in graphs. They used the name Mostar index for this invariant which is defined as MoG=∑uv∈EGnuuv,G−nvuv,G, where nuuv,G is the number of vertices of G closer to u than to v, and similarly, nvuv,G is the number of vertices closer to v than to u. They determined the extremal values of this invariant and characterized extremal trees and unicyclic graphs with respect to the Mostar index. Arockiaraj et al. [3] introduced the edge Mostar of the graph G as MoeG=∑e=uv∈EGmue,G−mve,G, where mue,G and mve,G are the number of edges of G lying closer to the vertex u than v and the number of edges of G lying closer to the vertex v than to the vertex u. They computed the Mostar and edge Mostar indices of the family of coronoid and carbon nanocones. Imran et al. [4] computed the edge Mostar index of some graph operations. As a consequence of these calculations, they obtained the edge Mostar index of several classes of chemical graphs and nanostructures.Deng and Li [5] determined the catacondensed hexagonal systems with the least and the second-least Mostar indices. In another paper [6], these authors computed the extremal trees with respect to the Mostar index. Ghorbani et al. [7] proved that a graph G with MoG=1 has no cut edge and computed the Mostar index of the pentagonal nanocones. A connected graph with this property, in which any two graph cycles have no edge in common, is called a cactus graph. Hayat and Zhou [8] determined all n−vertex cacti with maximum Mostar index and gave a sharp upper bound for the Mostar index of n−vertex cacti containing k cycles. The same authors in [9] constructed n−vertex trees with maximum Mostar index and fixed the maximum degree, diameter, or number of pendent vertices. Huang et al. [10] found the extremal hexagonal chains with respect to Mostar index, and Xiao et al. [11] computed the first three minimum of Mostar index in the class of hexagonal chains. Finally, Tepeh [12] proved a conjecture of Dosˇlić et al. [2] about the characterization of bicyclic graphs with a given number of vertices, for which extremal values of the Mostar index are attained.Our calculations are done with the aid of Nauty [13] and Matlab [14]. Our codes are accessible from the authors upon request.


## 2. Mostar Index

A vertexv in a given graph G is called a starlike vertex if degGv≥2 and u:uv∈EGanddegGu=1≥degGv−1. The set of all such vertices is denoted by SVG, and we use the name starlike set for SVG.Transformation 1.
We assume thatT is a tree and v∈SVT. We also assume that uv∈ET, degGu≠1, and x:xv∈ETandx≠u=v1,v2,…,vdegGv−1. Define T′=T−vvi:i=1,2,…,degGv−1+uvi:i=1,2,…,degGv−1. The resulting tree has been illustrated in Figure 1.Figure 1
The trees (a)T and (b) T′ in Transformation 1.
(a)(b)Lemma 1.
LetT and T′ be the n−vertex trees described in Transformation 1. Then, MoT<MoT′.Proof.
By definition,MoT−MoT′=nuuv,T−nvuv,T−n−2. Since degTv, degTu≥2, and nuuv,T−nvuv,T<n−2. Therefore, MoT−MoT′<0.
A caterpillar is a tree in which all the vertices are within distance 1 of a central path [15]. Let T be a caterpillar with the central path Pk:=v1v2,…,vk and di, 1≤i≤k, be the number of pendent vertices that are in distance 1 of a vertex vi. Then, we use the notation Pk1d1,2d2,…,kdk instead of T. Note that if di=0, 1≤i≤k, then we refuse to write idi in Pk1d1,2d2,…,kdk, see Figure 2.Figure 2
The caterpillarP523,42,54.Transformation 2.
We assume thatTc is a caterpillar with the longest path P:=v1v2,…,vk. We also assume that Q:=vlvl+1,…,vj, 1<l<j<k−1, is an internal path in Tc such that nvj−1vj−1vj,Tc≤nvjvj−1vj,Tc and x:xvl∈ETcandx∉vl−1,vl+1=w1,w2,…,wdegTcvl−2. Define(1)Tc′=Tc−wivl:i=1,2,…,degTcvl−2+wivj:i=1,2,…,degTcvl−2.
The resulting tree has been illustrated in Figure3.Figure 3
The trees (a)Tc, (b) Tc′, and (c) Tc″ in Transformations 2 and 3.
(a)(b)(c)Lemma 2.
LetTc and Tc′ be two trees in Transformation 2 with n vertices. Then, MoTc<MoTc′.Proof.
We consider two cases as follows:(1)
j=l+1. By definition of Tc and Tc′, we have(2)MoTc−MoTc′=nvjvlvj,Tc−nvlvlvj,Tc−nvjvlvj,Tc+degTcvl−2−nvlvlvj,Tc+degTcvl−2=4−2degTcvl<0.(2)
j≥l+2. Again by definition of Tc and Tc′, we have(3)MoTc−MoTc′=∑i=lj−1nvi+1vivi+1,Tc+j−i−nvivivi+1,Tc+i−l−∑i=lj−1nvi+1vivi+1,Tc+j−i+degTcvl−2−nvivivi+1,Tc+i−l−degTcvl+2=∑i=lj−14−2degTcvl<0,proving the lemma.Transformation 3.
We assume thatTc, P, Q, and w1,w2,…,wdegTcvl−2 are defined in Transformation 2. We also assume that j≥l+2 and nvlvlvl+1,Tc<nvl+1vlvl+1,Tc. Define(4)Tc″=Tc−wivl:i=1,2,…,degTcvl−2+wivl+1:i=1,2,…,degTcvl−2.
The resulting tree has been illustrated in Figure3.Lemma 3.
LetTc and Tc′′ be two trees in Transformation 3 with n vertices. Then, MoTc<MoTc″.Proof.
By definition ofTc and Tc″,(5)MoTc−MoTc″=nvl+1vlvl+1,Tc−nvlvlvl+1,Tc−nvl+1vlvl+1,Tc+degTcvl−2−nvlvlvl+1,Tc+degTcvl−2=4−2degTcvl<0,proving the lemma.Lemma 4.
Letn, k, and r be three positive integers such that k<n and 1≤r≤n−k. If r<⌈n−k/2⌉, then MoPn−krk<MoPn−kr+1k.Proof.
By definition,MoPn−krk−MoPn−kr+1k=r+k−n−k−r−n−2r≤max−2n−k−2r,−2k<0, as desired.Proposition 1.
LetT be a tree on n vertices. If T≅Prst, where r=diamT+1, s=⌈diamT+1/2⌉, and t=n−r, then(6)MoT=n2−3n−12diamT2+diamT+2,2∣diamT,n2−3n−12diamT2+diamT+32,2∣diamT−1.Proof.
SupposediamT=d. By definition of caterpillar,(7)MoT=2n−2+n−4+⋯+n−d+n−d−1n−2,2|d,2n−2+n−4+⋯+n−d+1+n−d−1n−1,2|d−1,and by simple calculations,(8)MoT=n2−3n−12d2+d+2,2|d,n2−3n−12d2+d+32,2|d−1,proving the lemma.Theorem 1.
LetT be a tree with n vertices. Then,(9)MoT≤n2−3n−12diamT2+diamT+2,2|diamT,n2−3n−12diamT2+diamT+32,2|diamT−1,with equality if and only if T≅Prst, where r=diamT+1, s=⌈diamT+1/2⌉, and t=n−r.Proof.
IfT≅Prst, where r=diamT+1, s=⌈diamT+1/2⌉, and t=n−r, then Proposition 1 gives the result. Otherwise, we assume that P:=v1v2,…,vdiamT+1 is the longest path in T. At first, by repeated applications of Transformation 1 on vertices of SVT\v2,vdiamT, we arrive at a caterpillar Tc with central path P. We now apply Lemma 1 to deduce that MoT≤MoTc. Next, by the repeated applications of Transformations 2 and 3 on the internal paths in Tc, we arrive at a caterpillar Prst, where r=diamT+1, 2≤s≤diamT, and t=n−r. Apply Lemmas 2 and 3 to prove that MoT≤MoTc≤MoPrst. Finally, by Lemma 4,(10)MoT≤n2−3n−12diamT2+diamT+2,2|diamT,n2−3n−12diamT2+diamT+32,2|diamT−1,with equality if and only if T≅Prst, where r=diamT+1, s=⌈diamT+1/2⌉, and t=n−r.Lemma 5.
Letn and r be two positive integers. If 1≤r≤n−r−4, then,(11)MoP42r−1,3n−r−3=MoP42r,3n−r−4+2.Proof.
By definition,MoP42r−1,3n−r−3−MoP42r,3n−r−4=n−r−1−r+1−n−r−2−r+2=2.Theorem 2.
LetT be an n−vertex tree and(12)T∉P32n−3,P42n−4,P42n−5,31,P53n−5.See Figure4, for details. Then,(13)MoT<MoP53n−5=MoP42n−5,31<MoP42n−4<MoP32n−3.Figure 4
The trees in Theorems2 and 3. (a) P32n−3. (b) P42n−4. (c) P42n−5,31. (d) Pn−111. (e) Pn−121. (f) Pn−131. (g) Pn−141. (h) Pn−222. (i) Pn−221,n−31. (j) Pn−231,n−31.
(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)Proof.
By definition,(14)MoP53n−5=MoP42n−5,31=n2−3n−2,MoP42n−4=nn−3,MoP32n−3=n−1n−2,so MoP53n−5=MoP42n−5,31<MoP42n−4<MoP32n−3. Since T∉P32n−3,P42n−4,P42n−5,31,P53n−5, diamT≥3. If diamT=3, then, by Lemma 5, MoT<MoP42n−5,31. If diamT≥4, then, by repeated applications of Transformation 1 on elements of SVT, we arrive at a tree Tx with diamTx=4. By Lemma 1, MoT≤MoTx, and by Theorem 1, MoTx≤MoP53n−5. The equality holds if and only if Tx≅P53n−5, as desired.Lemma 6.
Leta, b, and c be three positive integers such that a<b. Then, a+c−b<b+c−a.Proof.
Supposeι=b−a. Then, a+c−b−b+c−a=c−ι−c+ι<0.Transformation 4.
(see [16]). Suppose that w is a vertex in a connected graph G with at least two vertices and Nw,G=x1,x2,…,xdGw. In addition, we assume that P:ukuk−1,…,u2u1 and Q:vℓvℓ−1,…,v2v1, are two paths of lengths k and ℓ, k≥ℓ≥1, respectively. Let G1 be the graph obtained from G, P, and Q by attaching edges vℓw, wuk, and G2=G1−wxi:xi∈Nw,G+vℓxi:xi∈Nw,G. The graphs G1 and G2 have been illustrated in Figure 5.Figure 5
The graphsP, Q, G, G1, and G2 in Transformation 4. (a) G1. (b) G2.
(a)(b)Lemma 7.
LetG1 and G2 be two graphs in Transformation 3 on n vertices. Then, MoG2<MoG1.Proof.
SupposeVG=c. By definition of G1 and G2, we have(15)MoG1−MoG2=k+c−l−l+c−1−k+1=k+1+c−1−l−l+c−1−k+1,and Lemma 6 gives the result.Remark 1.
In Transformation4, if we replace the path P by a tree on k vertices, then again Lemma 7 is valid.Corollary 1.
The pathPn and the caterpillar Pn−121 have the first and second minimum Mostar index among all trees on n vertices, respectively.Proposition 2.
Letn≥8 be a positive integer.(1)
Ifn is odd, then MoPn−222=1/2n−12+6, MoPn−221,31=1/2n−12+8, MoPn−221,n−31=1/2n−12+4, MoPn−231,n−31=1/2n−12+6, MoPn−111=1/2n−12, MoPn−121=1/2n−12+2, MoPn−131=1/2n−12+4, and MoPn−141=1/2n−12+6.(2)
Ifn is even, then MoPn−222=1/2n−12+11/2, MoPn−221,31=1/2n−12+15/2, MoPn−221,n−31=1/2n−12+7/2, MoPn−231,n−31=1/2n−12+11/2, MoPn−111=1/2n−12−1/2, MoPn−121=1/2n−12+3/2, MoPn−131=1/2n−12+7/2, and MoPn−141=1/2n−12+11/2.Theorem 3.
LetT be a tree on n≥8 vertices. If(16)T∉Pn−1i1|1≤i≤4∪Pn−222,Pn−221,n−31,Pn−231,n−31,then(17)MoPn−111<MoPn−121<MoPn−131=MoPn−221,n−31<MoPn−141=MoPn−231,n−31=MoPn−222<MoT.Proof.
By Proposition2,(18)MoPn−111<MoPn−121<MoPn−131=MoPn−221,n−31<MoPn−141=MoPn−231,n−31=MoPn−222.
We now apply repeated applications of Transformation4 on the pendent paths in T to arrive at a caterpillar Tc in the set Pn−141,Pn−222,Pn−231,n−31 (Figure 4). Now, by Lemma 7, MoTc<MoT. Therefore, by Proposition 2,(19)MoPn−141=MoPn−231,n−31=MoPn−222<MoT,and this gives the result.


## 3. Edge Mostar Index

The aim of this section is to compare the Mostar and edge Mostar indices of trees and unicyclic graphs. We also present a proof for Conjecture 5.5 of Liu et al. [17]. In the end of this section, conjectures on the minimum of edge Mostar index of tricyclic, tetracyclic, and pentacyclic graphs are presented. Suppose G is a connected graph and E′⊆EG. Define MoE′=∑e=uv∈E′nue,G−nve,G and MoeE′=∑e=uv∈E′mue,G−mve,G.Proposition 3.
IfT is a tree, then MoeT=MoT.Proof.
Supposee=uv∈T and the trees Tu and Tv are components of T−e such that u∈VTu and v∈VTv. By definition, mue,T=ETu, mve,T=ETv, nue,T=VTu, and nve,T=VTv. The result follows from these facts that ETu=VTu−1 and ETv=VTv−1.Remark 2.
SupposeT is a tree. In Proposition 3, it is proved that the Mostar and edge Mostar indices of trees are equal. This shows that the edge version of all results in Section 2 containing Lemmas 1– 5, 7, Theorems 1–3, and Corollary 1 are correct.
Note that the converse of Proposition3 is not generally correct. For example, MoCn=MoeCn=0, for each cycle Cn of length n.
SupposeG is connected graph which is not a tree, e=uv is a cut edge of G and Gu and Gv are components of G−e. If one of Gu or Gv is a tree, then the edge e is said to be a tree-like cut edge of G and the number of vertices in the acyclic component of G−e is denoted by we. Furthermore, the set of all tree-like cut edges of G is denoted by CTG. A tree-like cut edge of G is said to be strong (weak), if the number of vertices in the acyclic component of G−e is greater than (less than) the number of vertices in another component of G−e. The set of all strong and weak tree-like cut edges of G are denoted by CTStG and CTWG, respectively.Proposition 4.
IfG is not acyclic graph, e1=x1y1 and e2=x2y2∈CTStG, then we1≠we2Proof.
SupposeGx1 and Gy1 are two components of G−e1 and Gx2 and Gy2 are two components of G−e2. Without loss of generality, we can assume that Gy1 and Gy2 are trees. Since e1,e2∈CTStG, Gy1 is a subgraph of Gy2 or Gy2 is a subgraph of Gy1, as desired.Proposition 5.
IfG is not an acyclic graph and CTStG≥1, then GCTStG is a path.Proof.
SupposeCTStG=e1=x1y1,e2=x2y2,…,ek=xkyk and we1>we2>⋯>wek. We also assume that Gx1 and Gy1 are two components of G−e1. Without loss of generality, we can assume that Gy1 is a tree. Since all edges of a tree is a cut edge, e2∈CTStG and we2=maxwe2,we3,…,wek, it can be proved that x2=y1 or y2=y1. Choose the edge e2 and repeat this process to complete the proof.Proposition 6.
IfG is not acyclic, then CTStG≤CTWG.Proof.
SupposeCTStG=e1=x1y1,e2=x2y2,…,ek=xkyk and we1>we2>⋯>wek. We also assume that Gxk and Gyk are two components of G−ek. Without loss of generality, it can be assumed that Gyk is a tree. Since ek∈CTStG, VGxk<VGyk. On the contrary, wek=minwe1,we2,we3,…,wek and e∈EGyk implies that e∈CTWG. Apply Proposition 5 and the fact that a cut edge cannot be on a cycle to complete our argument.Corollary 2.
Supposeγ is the cyclomatic number of a connected graph G with CTStG≥1; then,(1)
Ifγ=1, then CTStG≤CTWG–2.(2)
Ifγ=2, then CTStG≤CTWG–3.Lemma 8.
LetG be γ−cyclic graph such that CTG≥1; then,(1)
Ifγ=1, then MoeCTG≥MoCTG+1.(2)
Ifγ=2, then MoeCTG≥MoCTG+2.Proof.
Supposee=uv∈CTG; Gu and Gv are components of G−e such that u∈VGu, v∈VGv, and Gu is a tree. By definition, mue,T=EGu, mve,G=EGv, nue,G=VGu, and nve,G=VGv. Our main proof will consider two cases as follows:(1)
γ=1. In this case, EGu=VGu−1 and EGv=VTv. Thus,(20)MoeCTG=MoeCTStG+MoeCTWG=∑e=uv∈CTStGnue,G−1−nve,G+∑e=uv∈CTWGnue,G−1−nve,G=∑e=uv∈CTStGnue,G−nve,G−1+∑e=uv∈CTWGnue,G−nve,G+1=MoCTG−∑e=uv∈CTStG1+∑e=uv∈CTWG1.Now, by Corollary2, MoeCTG≥MoCTG+1.(2)
γ=2. In this case, EGu=VGu−1 and EGv=VTv+1. Hence,(21)MoeCTG=MoeCTStG+MoeCTWG=∑e=uv∈CTStGnue,G−1−nve,G−1+∑e=uv∈CTWGnue,G−1−nve,G−1≥∑e=uv∈CTStGnue,G−nve,G−2+∑e=uv∈CTWGnue,G−nve,G+2=MoCTG−∑e=uv∈CTStG2+∑e=uv∈CTWG2.Again by Corollary2, MoeCTG≥MoCTG+2.This completes the proof.
Supposek≥3 is a positive integer and Ti, 1≤i≤k, is a tree with a given vertex vi. Define the unicyclic graph Γk with vertex set VΓk=∪i=1kVTi and edge set EΓk=∪i=1kETi∪vivi+1:1≤i≤k−1∪v1vk.Lemma 9.
LetΓk be the graph defined above. If E1Γk=vivi+1:1≤i≤k−1∪v1vk, then MoeE1Γk=MoE1Γk.Proof.
Supposee=vi1vi2 is an arbitrary edge in E1Γk. Consider the following two cases:(1)
k is even. In this case, there exists a unique edge as f=vj1vj2∈E1Γk\vi1vi2 such that dΓkvi1,vj1=dΓkvi2,vj2. Therefore, nvi1e,Γk−nvi1e,Γk=nvi1e,Γk−f−nvi1e,Γk−f and mvi1e,Γk−mvi1e,Γk=mvi1e,Γk−f−mvi1e,Γk−f.(2)
k is odd. There exists a unique vertex vl in v1,v2,…,vk\vi1,vi2 such that dΓkvi1,vl=dΓkvi2,vl. We construct the tree Γk1 from the graph Γk by removing the vertices of Tl. Then, nvi1e,Γk−nvi1e,Γk=nvi1e,Γk1−nvi1e,Γk1 and mvi1e,Γk−mvi1e,Γk=mvi1e,Γk1−mvi1e,Γk1.
Now, the proof follows from cases (1), (2), and Proposition3.Theorem 4.
IfG is a unicyclic graph, then MoG≤MoeG with equality if and only if G≅Cn.Proof.
The proof follows from Lemmas8 and 9.Proposition 7.
LetΘ2,2,n−3 be an n−vertex bicyclic graph, n≥8, depicted in Figure 6. Then, MoeΘ2,2,n−3=2n−4.Figure 6
The bicyclic graphΘ2,2,n−3.Proof.
ife=uv∈v1vn,v1vn−1,vn−2vn,vn−2vn−1, then, by the structure of Θ2,2,n−3, mue,G−mve,G=n−3/2−n−5/2=1. We first assume that n is even. If i=n−2/2, then mvie,G−mvi+1e,G=0. If 1≤i≠n−2/2≤n−3 and e=vivi+1, then mvie,G−mvi+1e,G=5−3=2. Next, we assume that n is odd. If i=n−1/2,n+1/2 and e=vivi+1, then mvie,G−mvi+1e,G=1. If 1≤i≠n−1/2,n+1/2≤n−3 and e=vivi+1, then mvie,G−mvi+1e,G=5−3=2. Now, the result follows from above discussions and some easy calculations.
The following result is an immediate consequence of the pendent path and some easy calculations.Proposition 8.
LetP:=v1v2,…,vk be pendent path in an n−vertex bicyclic graph G. If k≥2, we choose the edge e=v1v2 and if k≥3, we choose f=v2v3. Then, mv1e,G−mv2e,G=n and mv2f,G−mv3f,G=n−2.Corollary 3.
LetG be an n−vertex bicyclic graph. If G has at least two pendent path of order ≥2 or one pendent path of order ≥3, then MoeG≥2n−2.
Supposek,l, and r are positive integers. Consider Ti, Rj, and Ft to be trees with these properties that vi∈VTi, uj∈VRj, wt∈VFt, 1≤i≤k, 1≤j≤l, and 1≤t≤r. Define four classes of bicyclic graphs denoted by Λk,l,r, k,l,r≥2, Υk,l, k≥3,l≥2, Ψk,l, k≥3,l≥1,k≥l, and Φk,l,r, l≥k≥r and k,r≥1,l≥2, with the following vertex and edge sets:(22)VΛk,l,r=∪i=1kVTi∪∪i=1lVRi∪∪i=rkVFi,VΥk,l=∪i=1kVTi∪∪i=1lVRi,VΨk,l=∪i=1kVTi∪∪i=1lVRi,VΦk,l,r=∪i=1kVTi∪∪i=1lVRi∪∪i=rkVFi,EΛk,l,r=∪i=1kETi∪∪i=lkERi∪∪i=rkEFi∪vivi+1:1≤i≤k−1∪uiui+1:1≤i≤l−1∪wiwi+1:1≤i≤r−1∪v1w1,w1vk,u1wr,wrul,EΥk,l=∪i=1kETi∪∪i=lkERi∪vivi+1:1≤i≤k−1∪uiui+1:1≤i≤l−1∪v1vk,v1u1,v1ul,EΨk,l=∪i=1kETi∪∪i=lkERi∪vivi+1:1≤i≤k−1∪uiui+1:1≤i≤l−1∪v1vk,v1u1,vkul,EΦk,l,r=∪i=1kETi∪∪i=lkERi∪∪i=rkEFi∪vivi+1:1≤i≤k−1∪uiui+1:1≤i≤l−1∪wiwi+1:1≤i≤r−1∪v1u1,u1w1,vkul,ulwr.
If, for eachT in the set Ti:i=1,…,k∪Ri:i=1,…,l∪Fi:i=1,…,r, VT=1, then we use the notation Θk,l,r as Φk,l,r.Lemma 10.
Ifn≥9, then MoeΛk,l,r≥2n−3.Proof.
DefineA=Ti|1≤i≤k∪Ri|1≤i≤l∪Fi|1≤i≤r. If, for trees T,T′∈A, we have VT∪VT′≥4, then the result follows from Corollary 3. If these exists a tree T∈A such that ET=e=uv, then mue,Λk,l,r−mve,Λk,l,r=n. On the contrary, there are at most three edges such as f=xy in EΛk,l,r\e=uv such that mxf,Λk,l,r−myf,Λk,l,r=0. So, in this case, MoeΛk,l,r≥2n−3. We now assume that, for every T∈A, VT=1. Then, there are at most three edges such as f1=x1y1 such that mx1f1,G−my1f1,G=0, there are at most two edges as f2=x2y2 with mx2f2,Λk,l,r−my2f2,Λk,l,r=1, there are at most two edges such as f3=x3y3 such that mx3f3,Λk,l,r−my3f3,Λk,l,r=2, there are at most two edges such as f4=x4y4 such that mx4f4,Λk,l,r−my4f4,Λk,l,r=3, and for other edges such as f5=x5y5, mx5f5,Λk,l,r−my5f5,Λk,l,r≥4. Therefore, MoeΛk,l,r≥4n−20, proving the lemma.Lemma 11.
Ifn≥9, then MoeΥk,l≥2n−3.Proof.
SupposeB=Ti:i=1,…,k∪Ri:i=1,…,l. If for two trees T,T′ in B, VT∪VT′≥4, then the result follows from Corollary 3. If there exists a tree T in B such that ET=e=uv, then mue,Υk,l−mve,Υk,l=n. Since there are at most two edges such as f=xy∈EΥk,l\e=uv such that mxf,Υk,l−myf,Υk,l=0, MoeΥk,l≥2n−2. We now assume that, for every T∈B, VT=1. Then, there are at most two edges as f1=x1y1 such that mx1f1,Υk,l−my1f1,Υk,l=0 and for other edges this value is ≥3. Therefore, MoeΥk,l≥3n−3.Lemma 12.
Ifn≥9, then MoeΨk,l≥2n−3.Proof.
SupposeB=Ti:i=1,…,k∪Ri:i=1,…,l. If, for trees T,T′∈B, VT∪VT′≥4, then the result follows from Corollary 3. If there exists a tree T∈B such that ET=e=uv, then mue,Ψk,l−mve,Ψk,l=n. Also, for e1=v1u1 and f=vkuk, we have mv1e1,Ψk,l−mu1e1,Ψk,l≥2 and mvkf,Ψk,l−mukf,Ψk,l≥2. Since there are at most three edges as f1=xy∈EΨk,l\e,e1,f such that mxf1,Ψk,l−myf1,Ψk,l=0, MoeG≥2n−1.
We now assume that, for eachT∈B, VT=1. If l=1, then(23)MoeG=3n−8,2|n,3n−7,2|n−1,as desired. Suppose l≥2. We consider two cases as follows:(1)
n is even. Since n≥9, mv1e,G−mu1e,G=k−1≥5 and mvkf,G−mukf,G=k−1≥5. Again, there are at most three edges such as f2=x2y2 such that mx2f2,G−my2f2,G=0, there are at most four edges f3=x3y3 such that mx3f3,G−my3f3,G=1, and, for other edges, this quantity is at most 2. Thus, MoeG≥2n−2.(2)
n is odd. Since n≥9, mv1e,G−mu1e,G=k−1≥4 and mvkf,G−mukf,G=k−1≥4. There are two edges such as f2=x2y2 such that mx2f2,G−my2f2,G=0, there are at most two edges as f3=x3y3 such that mx3f3,G−my3f3,G=1, and, for other edges, this value is at most 2. Hence, MoeG≥2n.
Hence, the result.Lemma 13.
Ifn≥9, then MoeΦk,l,r≥2n−4, with equality if and only if G≅Θ2,2,n−3.Proof.
Suppose thatA=Ti:i=1,…,k∪Ri:i=1,…,l∪Fi:i=1,…,r. If, for trees T,T′∈A, VT∪VT′≥4, the proof follows from Corollary 3. If there exists a tree T∈A with ET=e=uv, then mue,G−mve,G=n. On the contrary, there are at most three edges f=xy∈EG\e=uv such that mxf,G−myf,G=0. Thus, MoeG≥2n−3. Next, we assume that, for each T∈A, VT=1. Suppose 0≤ε0≤3 are the number of distinct edges as f1=x1y1 such that mx1f1,G−my1f1,G=0. Then, there are exactly 23−ε0 edges such as f2=x2y2 such that mx2f2,G−my2f2,G=1. Also, for e′=x′y′∈e1=u1u2,e2=ul−1ul, we have mx′e′,G−my′e′,G≥3 and for other edges, this quantity is ≥2. Therefore, MoeG≥2n−2−ε0−23−ε0+23−ε0+6=2n−4, with equality if and only if G≅Θ2,2,n−3.
We are now ready to prove Conjecture 5.5 in [17], see Figure 6.Theorem 5.
IfG is a bicyclic graph of order n≥9, then MoeG≥2n−4 and equality is occurred if and only if G≅Θ2,2,n−3.Proof.
The proof follows from Lemmas10–13.
In Figure7 and Table 1, the data of the bicyclic graphs with minimum edge Mostar index of order 4≤n≤8 are given.Figure 7
Bicyclic graphs with minimum edge Mostar index of order4≤n≤8. (a) G4. (b) G5. (c) G6. (d) G71. (e) G72. (f) G81. (g) G82.
(a)(b)(c)(d)(e)(f)(g)Table 1
The edge Mostar index of graphs in Figure7.
GraphsMoeG44G56G68G7i10i=1,2G8i12i=1,2


## 4. Concluding remarks

The aim of this section is to compute some examples about invariants presented in Sections1–3 and then suggest some conjectures.Example 1.
LetSn1, Gx,y, and Tlk be three graphs depicted in Figures 8–10, such that n≥3, x,y≥1, k≥0, and l≥2. Then,(24)MoSn1=n2−3n,MoeSn1=n2−2n−3,MoGx,y=3x+y+7+3,x−y=0,3x+y+7,x−y=1,3x+y+7+1,x−y=2,3x+y+7+2,x−y=3,MoeGx,y=2x+y+7+14,x−y=0,2x+y+7+10,x−y=1,2x+y+7+12,x−y=2,2x+y+7+16,x−y=3,MoTlk=MoeTlk=12l2k2l+3kl−6k+l−2,2|l,32kl2−3kl+12k+12l2−l+k2l2+12,2∤l.
By Example1, MoeSn1−MoSn1=n−3 and(25)MoGx,y−MoeGx,y=x+y−4,x−y=0or2,x+y−3,x−y=1,x+y−7,x−y=3.Figure 8
The unicyclic graphSn1.Figure 9
The bicyclic graphGx,y.Figure 10
The caterpillar treeTlk.Remark 3.
Letn be a positive integer.(1)
If5≤n≤9, then, in Figure 11 and Table 2, all tricyclic graphs with minimum edge Mostar index are given.(2)
If6≤n≤18, then, in Figure 12 and Table 3, all tetracyclic graphs with minimum edge Mostar index are given.(3)
If7≤n≤13, then, in Figure 13 and Table 4, all pentacyclic graphs with minimum edge Mostar index are given.
Our calculations with Nauty [13] on graphs with at most 22 vertices suggest the following conjecture.Figure 11
Tricyclic graphs with minimum edge Mostar index of ordern, 5≤n≤9. (a) G5. (b) G6. (c) G7. (d) G8. (e) G91. (f) G92. (g) G93.
(a)(b)(c)(d)(e)(f)(g)Table 2
The edge Mostar index of graphs in Figure11.
GraphsMoeG54G66G79G812G9i161≤i≤3Figure 12
Tetracyclic graphs with minimum edge Mostar index of ordern, 6≤n≤18. (a) G61. (b) G62. (c) G7. (d) G8. (e) G9. (f) G10. (g) G11. (h) G121. (i) G122. (j) G13. (k) G14. (l) G15. (m) G161. (n) G162. (o) G171. (p) G172. (q) G181. (r) G182. (s) G183. (t) G184. (u) G185.
(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)(m)(n)(o)(p)(q)(r)(s)(t)(u)Table 3
The edge Mostar index of graphs in Figure12.
GraphsMoeG6i0i=1,2G78G811G96G1014G1118G12i12i=1,2G1320G1416G1518G16i20i=1,2G17i22i=1,2G18i24i=1,2,3,4,5Figure 13
Pentacyclic graphs with minimum edge Mostar index of ordern, 7≤n≤13. (a) G7. (b) G81. (c) G82. (d) G9. (e) G101. (f) G102. (g) G103. (h) G104. (i) G111. (j) G112. (k) G12. (l) G13.
(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)Table 4
The edge Mostar index of graphs in Figure13.
GraphsMoeG78G8i0i=1,2G98G10i161≤i≤4G11i12i=1,2G1210G1312Conjecture 1.
SupposeG is a graph with n vertices.(1)
SupposeG is a tricyclic graph and n≥10. If n is odd, then MoeG≥16, and the equality holds if and only if G≅Godd, see Figure 14. If n is even, then MoeG≥14, and the equality holds if and only if G≅Geven, see Figure 14, for details.(2)
SupposeG is an n−vertex tetracyclic graph, n≥19. If n is odd, then MoeG≥n+5, and the equality holds if and only if G≅Godd, see Figure 15. If n is even, then MoeG≥24, and the equality holds if and only if G≅Geven, see Figure 15, for details.(3)
SupposeG is a pentacyclic graph and n≥14. If n is odd, then MoeG≥n+1, and the equality if and only if G≅Godd, see Figure 16. If n is even, then MoeG≥n−2, with equality if and only if G≅Geven, see Figure 16, for details.Figure 14
Tricyclic graphs with minimum edge Mostar index of ordern, n≥10. (a) Geven. (b) Godd.
(a)(b)Figure 15
Tetracyclic graphs with minimum edge Mostar index of ordern≥19. (a) Godd. (b) Geven.
(a)(b)Figure 16
Pentacyclic graphs with minimum edge Mostar index of odern≥14. (a) Geven. (b) Godd.
(a)(b)



---

*Source: 6651220-2021-04-10.xml*