The lower bound of revised edge-Szeged index of unicyclic graphs with given diameter

Abstract

Given a connected graph G, the revised edge-revised Szeged index is defined as S{z}_e^{\ast }\left(G\right)=\sum _{e=uv\in E_G}\left(m_u\right(e)+\frac{m_0\left(e\right)}{2})\left(m_v\right(e)+\frac{m_0\left(e\right)}{2}), where m_u\left(e\right), m_v\left(e\right) and m_0\left(e\right) are the number of edges of G lying closer to vertex u than to vertex v, the number of edges of G lying closer to vertex v than to vertex u and the number of edges of G at the same distance to u and v, respectively. In this paper, by transformation and calculation, the lower bound of revised edge-Szeged index of unicyclic graphs with given diameter is obtained, and the extremal graph is depicted.

Graphical abstract

Keywords

Wiener index / revised edge Szeged index / unicyclic graph / extremal graph

1 Introduction

All graphs considered in this paper are simple, finite, and undirected. For terminology and notation, please refer to [2]. Let G be a connected graph with vertex set V_G and edge set E_G, N_G(u) is the set of vertices in G adjacent to vertex u, d_G(u,v) denotes the distance between u and v in G. We call a vertex u be a pendent vertex if d(u)=1. The Wiener index of G is defined as

W(G)=\sum _{\{u,v\}\subseteq V_G}{d}_G(u,v).

The definition of the index has been widely used in many mathematical literature, such as [5, 7, 10, 11, 19].

Let e=uv be an edge of G, and define three sets as follows:

N_0(e|G)=\{w\in V_G:d_G(u,w)=d_G(v,w)\}.

Thus, \{N_u(e|G),N_v(e|G),N_0(e|G)\} is a partition of the vertices of G. The number of vertices of N_u(e|G), N_v(e|G) and N_0(e|G) are denoted by n_u(e|G), n_v(e|G) and n_0(e|G), respectively. Evidently, if n is the number of vertices of the graph G, then n_u(e|G)+n_v(e|G)+n_0(e|G)=n.

Gutman [8] introduced the definition of the Szeged index as

\text{Sz}(G)=\sum _{e=uv\in E_G}{n}_u(e|G)n_v(e|G),

and \mathrm{R}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{i}\acute{c} [16] gave the definition of the revised Szeged index as

{\text{Sz}}^{\ast }(G)=\sum _{e=uv\in E_G}\left(n_u(e|G)+\frac{n_0(e|G)}{2}\right)\left(n_v(e|G)+\frac{n_0(e|G)}{2}\right).

For some properties and applications of these two indices, please refer to these literatures [1, 3, 4, 12, 15, 17, 20].

For edge e=uv\in E_G, the distance between e and the vertex w is denoted as d(w,e), which is defined as

d(w,e)=\mathrm{m}\mathrm{i}\mathrm{n}\{d(u,w),d(v,w)\}.

Let

M_0(e|G)=\{x\in E_G:d_G(u,x)=d_G(v,x)\}.

The number of edges of M_u(e|G),M_v(e|G) and M_0(e|G) are denoted by m_u(e|G), m_v(e|G) and m_0(e|G), respectively. Evidently, if m is the number of edges of the graph G, then m_u(e|G)+m_v(e|G)+m_0(e|G)=m.

Gutman [9] introduced the definition of the edge-Szeged index as

{\text{Sz}}_e(G)=\sum _{e=uv\in E_G}{m}_u(e|G)m_v(e|G).

Dong [6] introduced the definition of the revised edge-Szeged index as

{\text{Sz}}_e^{\ast }(G)=\sum _{e=uv\in E_G}\left(m_u(e|G)+\frac{m_0(e|G)}{2}\right)\left(m_v(e|G)+\frac{m_0(e|G)}{2}\right),

and gave the results of maximum and minimum revised edge-Szeged index of unicyclic graphs. Wang et al. [18] determined the lower bound of the edge-Szeged index of unicyclic graphs with given diameter. In 2016, Liu [13] gave the upper bound of revised edge-Szeged index of bicyclic graphs. Two years later, they got the lower bound of the revised edge-Szeged index of cactus [14]. In this paper, through transformation and calculation, the lower bound of the revised edge-Szeged index of unicyclic graphs with given diameter is obtained, and the extremal graph is depicted.

2 Preliminaries

An n\mathrm{t}\mathrm{h} order star is a graph in which one of the degree of vertices is n-1, and the remaining vertices are connected to that vertex. The vertex with degree is n-1 is called the center vertex of the star.

If a vertex v of a graph is connected to several pendant vertices, then the vertex is said to have pendant star. For convenience, the pendant star is marked as S_v, and |V_{S_v}|=s_v.

Fact 1　For random variable x(0⩽x⩽m), when x⩽\frac{m}{2}, the quadratic function f(x)=x(m-x) is strictly monotone increasing.

Fact 2　 a^2>a_1^2+a_2^2+\cdots +a_n^2(n⩾2), where a=a_1+a_2+\cdots +a_n and a_1,a_2,\dots ,a_n are numbers greater than 0.

Lemma 1　 For any simple and connected graph G, there is a pendant tree in G with v_i as the center vertex, denoted T_{v_i}. Delete all edges in T_{v_i}, connect v_i with the vertices in V_{T_{v_i}}, and note the changed graph as G^{\prime }. It is easy to get {\text{Sz}}_e^{\ast }(G)⩾{\text{Sz}}_e^{\ast }(G^{\prime }), with equality if and only if G\cong G^{\prime }.

Lemma 2　 Let{\omega }_1{\omega }_2be the cut edge of any simple and connected graphG, contracting{\omega }_1{\omega }_2to a vertex, say{\omega }_1, add the pendant edge{\omega }_1{\omega }_2at the{\omega }_1, note the changed graph asG^{\prime }. The specific graph is inFig. 1. Then{\text{Sz}}_e^{\ast }(G)-{\text{Sz}}_e^{\ast }(G^{\prime })⩾0, with equality if and only ifG\cong G^{\prime }.

Proof　Let G_1 and G_2 be branches of G-{\omega }_1{\omega }_2, where G_1 contains {\omega }_1, and G_2 contains {\omega }_2. For any e=uv\in E_{G_1}, if {\omega }_1{\omega }_2\in M_0(e)(M_u(e), M_v(e)), then E_{G_2}\subseteq M_0(e)(M_u(e), M_v(e)). Similarly, for any f=rs\in E_{G_2}, if {\omega }_1{\omega }_2\in M_0(f) (M_u(f), M_v(f)), then E_{G_1}\subseteq M_0(f)(M_u(f), M_v(f)).

So, for all e=uv\in E_{G_1}, we have

m_u(e|G)=m_u(e|G^{\prime }),m_v(e|G)=m_v(e|G^{\prime }),m_0(e|G)=m_0(e|G^{\prime }).

For all f=rs\in E_{G_2}, we have

m_r(f|G)=m_r(f|G^{\prime }),m_s(f|G)=m_s(f|G^{\prime }),m_0(f|G)=m_0(f|G^{\prime }).

Known that {\omega }_1{\omega }_2 is a cut edge in G and a pendant edge in G^{\prime }, so

m_{{\omega }_1}({\omega }_1{\omega }_2|G)=|E_{G_1}|,m_{{\omega }_2}({\omega }_1{\omega }_2|G)=|E_{G_2}|,m_0({\omega }_1{\omega }_2|G)=1,

m_{{\omega }_1}({\omega }_1{\omega }_2|G^{\prime })=|E_{G_1}|+|E_{G_2}|,m_{{\omega }_2}({\omega }_1{\omega }_2|G^{\prime })=0,m_0({\omega }_1{\omega }_2|G^{\prime })=1.

Summarizing above, there is

\begin{array}{rl}{\text{Sz}}_e^{\ast }(G)-{\text{Sz}}_e^{\ast }(G^{\prime })& =\sum _{e=uv\in E_G}\left(m_u(e|G)+\frac{m_0(e|G)}{2}\right)\left(m_v(e|G)+\frac{m_0(e|G)}{2}\right)\\ & -\sum _{e=uv\in E_{G^{\prime }}}\left(m_u(e|G^{\prime })+\frac{m_0(e|G^{\prime })}{2}\right)\left(m_v(e|G^{\prime })+\frac{m_0(e|G^{\prime })}{2}\right)\\ & =\left(|E_{G_1}|+\frac{1}{2}\right)\left(|E_{G_2}|+\frac{1}{2}\right)-\frac{1}{2}\left(|E_{G_1}|+|E_{G_2}|+\frac{1}{2}\right)\\ & =|E_{G_1}||E_{G_2}|⩾0,\end{array}

with equality if and only if |E_{G_1}||E_{G_2}|=0, that is {\omega }_1{\omega }_2 is a pendant edge in graph G.□

If the number of vertices of a simple and connected graph is equal to edges, then the graph is called unicyclic graph. The maximum distance between any two vertices in G is called the diameter of G. For convenience, let G_m^d be the set of all unicyclic graph with m edges and diameter d.

Theorem 1　 Let G be an unicyclic graph with m edges, where m⩾20, and let d be the diameter of G.

(1) If 3⩽d⩽6, then

{\text{Sz}}_e^{\ast }(G)⩾\frac{(2d^2+2m-10d+35)m}{4}-\frac{d^3-6d^2+11d+39}{3},

with equality if and only if G\cong G_5, see Fig. 4.

(2) If d⩾7, then

{\text{Sz}}_e^{\ast }(G)⩾\{\begin{array}{rl}& \frac{(d^2-2d+2m+24)m}{4}-\frac{d^3-d+180}{12},disodd;\\ & \frac{(d^2-2d+2m+23)m}{4}-\frac{d^3-4d+180}{12},diseven,\end{array}

with equality if and only ifG\cong G_1, seeFig. 2.

3 The proof of Theorem 1

Select G in G_m^d to make the revised edge-Szeged index of G as small as possible. Let P_{d+1}=u_0{u}_1{u}_2\cdots u_{d-1}{u}_d be the longest path in G. For convenience, let e_i=u_i{u}_{i+1}(i=0,1,\dots ,d-1). C_k is unique cycle in G, and the cycle length is k. According to Lemma 1, a pendant tree at any vertex on P_{d+1}(C_k) is a pendant star. According to Lemma 2, |V_{P_{d+1}}\bigcap V_{C_k}|⩾1 is known, so let's discuss it in two cases.

Case 1　 |V_{P_{d+1}}\bigcap V_{C_k}|=1, let V_{P_{d+1}}\bigcap V_{C_k}=\{u_i\}.

(1) First proof: In G, there is no pendant star at any vertex on C_k except u_i. Otherwise, suppose that there are pendant stars at certain vertices of C_k (other than u_i), and denote these vertices as . Move the pendant stars from v_{j_1},v_{j_2},\dots ,v_{j_r} to u_i, let the changed graph be G^{\prime }.

For convenience, let p_v be the number of edges of the pendant tree at vertex v on C_k, then \sum _{v\in V_{C_k}}{p}_v=m-k.

Through analysis, it is easy to know that for all e=uv\in E_G\mathrm{\setminus }{E}_{C_k}, m_u(e|G)=m_u(e|G^{\prime }), m_v(e|G)=m_v(e|G^{\prime }), m_0(e|G)=m_0(e|G^{\prime }).

Take any edge e_j=uw\in E_{C_k}. If k is odd, let the vertex is v where the distance from v to the two endpoints of e_j is equal, then

m_u(e_j|G)=\{\begin{array}{rl}& \frac{k-2}{2}+x_j,k\mathrm{i}\mathrm{s}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n};\\ & \frac{k-1}{2}+x_j,k\mathrm{i}\mathrm{s}\mathrm{o}\mathrm{d}\mathrm{d},\end{array}

m_w(e_j|G)=\{\begin{array}{rl}& \frac{k-2}{2}+y_j,k\mathrm{i}\mathrm{s}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n};\\ & \frac{k-1}{2}+y_j,k\mathrm{i}\mathrm{s}\mathrm{o}\mathrm{d}\mathrm{d},\end{array}

m_0(e_j|G)=\{\begin{array}{l}2,k\mathrm{i}\mathrm{s}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n};\\ p_v+1,k\mathrm{i}\mathrm{s}\mathrm{o}\mathrm{d}\mathrm{d},\end{array}

where x_j is the number of edges on E_G\mathrm{\setminus }{E}_{C_k} that are close to u, and y_j is the number of edges on E_G\mathrm{\setminus }{E}_{C_k} that are close to w. If k is even, then x_j+y_j=m-k. If k is odd, then x_j+y_j=m-k-p_v.

Notice that there is a vertex u(\ne u_i) on C_k that has a pendant star, let N_G(u)\bigcap V_{C_k}=\{w_1,w_2\}, then connect u and u_i have two paths, that is P_1=u{w}_1\cdots u_i, P_2=u{w}_2\cdots u_i. If |V_{P_1}|⩾|V_{P_2}|, for e_k=u{w}_2, then x_k>0,y_k>0. If , for e_k=u{w}_1, then x_k>0, y_k>0.

So, if k is even, then

\begin{array}{l}\begin{array}{rl}{\text{Sz}}_e^{\ast }(G)& -{\text{Sz}}_e^{\ast }(G^{\prime })\\ & =\sum _{j=1}^k\left(\frac{k-2}{2}+x_j+1\right)\left(\frac{k-2}{2}+y_j+1\right)\\ & -k\left(\frac{k-2}{2}+1\right)\left(m-\frac{k-2}{2}-1\right)\\ & =\sum _{j=1}^k\left(\frac{k}{2}+x_j\right)\left(\frac{k}{2}+y_j\right)-k\left(\frac{k}{2}\right)\left(m-\frac{k}{2}\right)\\ & =k{\left(\frac{k}{2}\right)}^2+\frac{k}{2}\sum _{j=1}^k(x_j+y_j)+\sum _{j=1}^k{x}_j{y}_j-k\left(\frac{k}{2}\right)\left(m-\frac{k}{2}\right)\\ & =k{\left(\frac{k}{2}\right)}^2+k\frac{k}{2}(m-k)+\sum _{j=1}^k{x}_j{y}_j-k\left(\frac{k}{2}\right)\left(m-\frac{k}{2}\right)\\ & =\sum _{j=1}^k{x}_j{y}_j\\ & ⩾x_k{y}_k>0.\end{array}\end{array}

If k is odd, then

\begin{array}{rl}{\text{Sz}}_e^{\ast }\left(G\right)& -{\text{Sz}}_e^{\ast }\left(G^{\prime }\right)\\ & =\sum _{j=1}^k\left(\frac{k}{2}+\frac{p_v}{2}+x_j\right)\left(\frac{k}{2}+\frac{p_v}{2}+y_j\right)-\left(k-1\right)\left(\frac{k}{2}\right)\left(m-\frac{k}{2}\right)-{\left(\frac{m}{2}\right)}^2\\ & =k{\left(\frac{k}{2}\right)}^2+\frac{k}{2}\sum _{j=1}^k\left(p_v+x_j+y_j\right)+\sum _{j=1}^k\left(\frac{p_v}{2}+x_j\right)\left(\frac{p_v}{2}+y_j\right)\\ & -\left(k-1\right)\left(\frac{k}{2}\right)\left(m-\frac{k}{2}\right)-{\left(\frac{m}{2}\right)}^2\\ & =\sum _{j=1}^k\left(\frac{p_v}{2}+x_j\right)\left(\frac{p_v}{2}+y_j\right)+\frac{k}{2}\left(m-\frac{k}{2}\right)-{\left(\frac{m}{2}\right)}^2\\ & =\sum _{j=1}^k{\frac{p_v}{4}}^2+\sum _{j=1}^k\frac{p_v}{2}\left(m-k-p_v\right)+\sum _{j=1}^k{x}_j{y}_j-{\left(\frac{m-k}{2}\right)}^2\end{array}

\begin{array}{rl}& =-\sum _{j=1}^k{\frac{p_v}{4}}^2+\frac{(m-k{)}^2}{2}+\sum _{j=1}^k{x}_j{y}_j-\frac{(m-k{)}^2}{4}\\ & =-\sum _{j=1}^k{\frac{p_v}{4}}^2+\frac{(m-k{)}^2}{4}+\sum _{j=1}^k{x}_j{y}_j\\ & >\sum _{j=1}^k{x}_j{y}_j(\mathrm{b}\mathrm{y}\mathrm{F}\mathrm{a}\mathrm{c}\mathrm{t}2)\\ & ⩾x_k{y}_k>0.\end{array}

Therefore, there are no pendant stars on C_k except vertex u_i.

(2) Second proof: If the length of C_k(k>4) is reduced to 4 in G, the revised edge-Szeged index is smaller. Suppose that the cycle length of C_k is greater than 4. Let N_G(u_i)\bigcap V_{C_k}=\{v_1,v_2\}, v_3 is a vertex on C_k besides u_i, v_1, v_2, let G^{\prime }=G-E_{C_k}+\bigcup _{x\in V_{C_k}\mathrm{\setminus }\{v_3\}}{u}_{i}x+v_1{v}_3+v_2{v}_3. Through analysis, it is easy to know that for all e=uv\in E_G\mathrm{\setminus }{E}_{C_k}, m_u(e|G)=m_u(e|G^{\prime }), m_v(e|G)=m_v(e|G^{\prime }), m_0(e|G)=m_0(e|G^{\prime }).

So, if k is even (k⩾6), then

\begin{array}{rl}{\text{Sz}}_e^{\ast }\left(G\right)-{\text{Sz}}_e^{\ast }\left(G^{\prime }\right)& =k\left(\frac{k}{2}\right)\left(m-\frac{k}{2}\right)-\left(k-4\right)\frac{1}{2}\left(m-\frac{1}{2}\right)-4\cdot 2\left(m-2\right)\\ & ⩾3k\left(m-3\right)-\left(\frac{k}{2}-2\right)\left(m-\frac{1}{2}\right)-8m+16\left(\mathrm{B}\mathrm{y}\mathrm{F}\mathrm{a}\mathrm{c}\mathrm{t}1\right)\\ & =k\left(\frac{5}{2}m-\frac{35}{4}\right)-6m+15\\ & ⩾9m-\frac{75}{2}>0.\end{array}

If k is odd (k⩾5), then

\begin{array}{rl}{\text{Sz}}_e^{\ast }\left(G\right)& -{\text{Sz}}_e^{\ast }\left(G^{\prime }\right)\\ & =\left(k-1\right)\left(\frac{k}{2}\right)\left(m-\frac{k}{2}\right)+{\left(\frac{m}{2}\right)}^2-\left(k-4\right)\frac{1}{2}\left(m-\frac{1}{2}\right)-4\cdot 2\left(m-2\right)\\ & ⩾\frac{5}{2}\left(k-1\right)\left(m-\frac{5}{2}\right)+{\left(\frac{m}{2}\right)}^2-\left(\frac{k}{2}-2\right)\left(m-\frac{1}{2}\right)\\ & -8m+16\left(\mathrm{B}\mathrm{y}\mathrm{F}\mathrm{a}\mathrm{c}\mathrm{t}1\right)\\ & =k\left(2m-6\right)+{\left(\frac{m}{2}\right)}^2-\frac{17}{2}m+\frac{85}{4}\\ & ⩾\frac{m^2}{4}+\frac{3}{2}m-\frac{35}{4}>0.\end{array}

(3) Third proof: There is no pendant star at any other vertices on P_{d+1} except u_i. Otherwise, without loss of generality, suppose that there is a pendant star at a vertex u_r on P_{d+1}, where . Next, we will discuss it in two cases:

(i) m_{u_r}(e_r|G)⩽m_{u_{r+1}}(e_r|G). Now, move the pendant star from u_r to u_{r+1}, and let the changed graph be G^{\prime }. Then, comparing G and G^{\prime }, it was found that for all e=uv\in E_G\mathrm{\setminus }{e}_r, m_u(e|G)=m_u(e|G^{\prime }), m_v(e|G)=m_v(e|G^{\prime }), m_0(e|G)=m_0(e|G^{\prime }). So

\begin{array}{rl}{\text{Sz}}_e^{\ast }\left(G\right)-{\text{Sz}}_e^{\ast }\left(G^{\prime }\right)& =\left(m_{u_r}\left(e_r|G\right)+\frac{1}{2}\right)\left(m_{u_{r+1}}\left(e_r|G\right)+\frac{1}{2}\right)\\ & -\left(m_{u_r}\left(e_r|G\right)-s_{u_r}+\frac{1}{2}\right)\left(m_{u_{r+1}}\left(e_r|G\right)+s_{u_r}+\frac{1}{2}\right)\\ & >0\left(\mathrm{b}\mathrm{y}\mathrm{F}\mathrm{a}\mathrm{c}\mathrm{t}1\right).\end{array}

(ii) m_{u_r}(e_r|G)>m_{u_{r+1}}(e_r|G). Because , m_{u_{i-1}}(e_{i-1}|G)>m_{u_i}(e_{i-1}|G). Now, move the unique cycle (the cycle length is 3 or 4) and the pendant star on u_i to u_{i-1}, and let the changed graph be G^{″}. Record the number of edges of the pendant star and the cycle on u_i as a. Compare G with G^{″}, it was found that for all e=uv\in E_G\mathrm{\setminus }{e}_{i-1}, m_u(e|G)=m_u(e|G^{″}), m_v(e|G)=m_v(e|G^{″}), m_0(e|G)=m_0(e|G^{″}). So

\begin{array}{rl}{\text{Sz}}_e^{\ast }\left(G\right)-{\text{Sz}}_e^{\ast }\left(G^{″}\right)& =\left(m_{u_{i-1}}\left(e_{i-1}|G\right)+\frac{1}{2}\right)\left(m_{u_i}\left(e_{i-1}|G\right)+\frac{1}{2}\right)\\ & -\left(m_{u_{i-1}}\left(e_{i-1}|G\right)+a+\frac{1}{2}\right)\left(m_{u_i}\left(e_{i-1}|G\right)-a+\frac{1}{2}\right)\\ & >0\left(\mathrm{b}\mathrm{y}\mathrm{F}\mathrm{a}\mathrm{c}\mathrm{t}1\right).\end{array}

Continue this process until all the pendant stars on P_{d+1} move to u_i.

(4) Fourth proof: when m⩾16, the revised edge-Szeged index of a cycle length of 4 is smaller than that of a cycle length of 3. It is known that G is a unicyclic graph with a cycle length of 4. Let C_4=u_i{v}_1{v}_2{v}_3{u}_i, G^{\prime }=G-v_1{v}_2-v_2{v}_3+v_1{v}_3+u_i{v}_2. Then, for all e=uv\in E_G\mathrm{\setminus }{E}_{C_4}, m_u(e|G)=m_u(e|G^{\prime }), m_v(e|G)=m_v(e|G^{\prime }), m_0(e|G)=m_0(e|G^{\prime }). So

\begin{array}{rl}{\text{Sz}}_e^{\ast }\left(G\right)-{\text{Sz}}_e^{\ast }\left(G^{\prime }\right)& =8\left(m-2\right)-\frac{1}{2}\left(m-\frac{1}{2}\right)-2\left(1+\frac{1}{2}\right)\left(m-1-\frac{1}{2}\right)-{\left(\frac{m}{2}\right)}^2\\ & =8m-16-\frac{1}{2}\left(m-\frac{1}{2}\right)-3\left(m-\frac{3}{2}\right)-{\left(\frac{m}{2}\right)}^2\\ & =-\frac{1}{4}\left(m^2-18m+45\right)\\ & =-\frac{1}{4}\left(m-3\right)\left(m-15\right).\end{array}

Therefore, when m⩾16, the revised edge-Szeged index of a unicyclic graph with a cycle length of 4 is smaller than a cycle length of 3.

(5) Final proof: u_i coincides with u_{\lfloor \frac{d}{2}\rfloor }. Otherwise, without loss of generality, suppose , then , . Now, move the pendant stars on C_4 and u_i to u_{i+1}, and let the changed graph be G^{\prime }. Compare G with G^{\prime }, it was found that for all e=uv\in E_G\mathrm{\setminus }{e}_i, m_u(e|G)=m_u(e|G^{\prime }), m_v(e|G)=m_v(e|G^{\prime }), m_0(e|G)=m_0(e|G^{\prime }). So

\begin{array}{rl}{\text{Sz}}_e^{\ast }\left(G\right)& -{\text{Sz}}_e^{\ast }\left(G^{\prime }\right)\\ & =\left(m_{u_i}\left(e_i|G\right)+\frac{1}{2}\right)\left(m_{u_{i+1}}\left(e_i|G\right)+\frac{1}{2}\right)\\ & -\left(m_{u_i}\left(e_i|G^{\prime }\right)+\frac{1}{2}\right)\left(m_{u_{i+1}}\left(e_i|G^{\prime }\right)+\frac{1}{2}\right)\\ & =\left(d_G\left(u_0,u_i\right)+m-d+\frac{1}{2}\right)\left(d_G\left(u_{i+1},u_d\right)+\frac{1}{2}\right)\\ & -\left(d_G\left(u_0,u_i\right)+\frac{1}{2}\right)\left(d_G\left(u_{i+1},u_d\right)+m-d+\frac{1}{2}\right)\\ & =\left(m-d\right)\left(d_G\left(u_{i+1},u_d\right)-d_G\left(u_0,u_i\right)\right)>0.\end{array}

Continue this process until u_i coincides with u_{\lfloor \frac{d}{2}\rfloor }.

To sum up, for all G\in G_m^d, if there is only one common vertex between the cycle and diameter in G, and m⩾16, then G_1 in Fig.2 is the graph corresponding to the minimum revised edge-Szeged index, and

{\text{Sz}}_e^{\ast }(G_1)=\{\begin{array}{r}\frac{(d^2-2d+24+2m)m}{4}-\frac{d^3-d+180}{12},d\mathrm{i}\mathrm{s}\mathrm{o}\mathrm{d}\mathrm{d};\\ \frac{(d^2-2d+23+2m)m}{4}-\frac{d^3-4d+180}{12},d\mathrm{i}\mathrm{s}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n}.\end{array}

Case 2　 |V_{P_{d+1}}\bigcap V_{C_k}|⩾2.

(1) First, consider |V_{P_{d+1}}\bigcap V_{C_k}|=2, k⩾5. In this case, let C_k=u_i{v}_1\cdots v_{k-2}{u}_{i+1}{u}_i, V_{P_{d+1}}\bigcap V_{C_k}=\{u_i,u_{i+1}\}. We apply the following transformations to G: contract the edge u_i{v}_1 to u_i, and then add the pendant edge u_i{v}_1 at u_i; contract the edge v_{\lfloor \frac{k}{2}\rfloor }{v}_{\lfloor \frac{k}{2}\rfloor +1} to v_{\lfloor \frac{k}{2}\rfloor }, and then add the pendant edge v_{\lfloor \frac{k}{2}\rfloor }{v}_{\lfloor \frac{k}{2}\rfloor +1} at v_{\lfloor \frac{k}{2}\rfloor }. Let the changed graph be G^{\prime }, G^{\prime } is a unicyclic graph with a cycle length of k-2.

When k is odd (k⩾5), for convenience, let e_1=v_{\lfloor \frac{k}{2}\rfloor }{v}_{\lfloor \frac{k}{2}\rfloor +1}, e_2=v_{\lfloor \frac{k}{2}\rfloor +1}v_{\lfloor \frac{k}{2}\rfloor +2}, e_3=v_{\lfloor \frac{k}{2}\rfloor }{v}_{\lfloor \frac{k}{2}\rfloor +2}, E_0=\{e_i,u_i{v}_1,e_1,e_2\}\subseteq G, E_1=\{e_i,u_i{v}_1,e_1,e_3\}\subseteq G^{\prime }. In G, let the number of edges near u_i of e_i and included in E_G\mathrm{\setminus }{E}_{C_k} be x_1, the number of edges near v_1 of v_1{u}_i and included in E_G\mathrm{\setminus }{E}_{C_K} be x_2, the number of edges near v_{\lfloor \frac{k}{2}\rfloor } of e_1 and included in E_G\mathrm{\setminus }{E}_{C_K} be x_3, the number of edges near v_{\lfloor \frac{k}{2}\rfloor +1} of e_2 and included in E_G\mathrm{\setminus }{E}_{C_K} be x_4. Let the number of edges of the pendant tree on v_{\lfloor \frac{k}{2}\rfloor } be t_1, the number of edges of the pendant tree on v_{\lfloor \frac{k}{2}\rfloor +1} be t_2, the number of edges of the pendant tree on u_i be t_3, the number of edges of the pendant tree on v_1 be t_4. Since that, there is x_2=x_3, x_1-x_2=t_3-t_1, x_4-x_3=t_2-t_4. By comparing G and G^{\prime }, it is easy to know

\begin{array}{rl}& {\text{Sz}}_e^{\ast }\left(G\right)-{\text{Sz}}_e^{\ast }\left(G^{\prime }\right)\\ & =\sum _{e=uv\in E_0}\left(m_u\left(e|G\right)+\frac{m_0\left(e|G\right)}{2}\right)\left(m_v\left(e|G\right)+\frac{m_0\left(e|G\right)}{2}\right)\\ & -\sum _{e=uv\in E_1}\left(m_u\left(e|G^{\prime }\right)+\frac{m_0\left(e|G^{\prime }\right)}{2}\right)\left(m_v\left(e|G^{\prime }\right)+\frac{m_0\left(e|G^{\prime }\right)}{2}\right)\\ & =\sum _{i=1}^4\left(x_i+\frac{k-1}{2}+\frac{t_i+1}{2}\right)\left[m-\left(x_i+\frac{k-1}{2}+\frac{t_i+1}{2}\right)\right]-2\cdot \frac{1}{2}\left(m-\frac{1}{2}\right)\\ & -\left(x_1+\frac{k-3}{2}+1+\frac{t_1+t_2+2}{2}\right)\left[m-\left(x_1+\frac{k-3}{2}+1+\frac{t_1+t_2+2}{2}\right)\right]\\ & -\left(x_4+\frac{k-3}{2}+1+\frac{t_3+t_4+2}{2}\right)\left[m-\left(x_4+\frac{k-3}{2}+1+\frac{t_3+t_4+2}{2}\right)\right]\\ & =\sum _{i=1}^4\left(x_i+\frac{k+t_i}{2}\right)\left[m-\left(x_i+\frac{k+t_i}{2}\right)\right]-\left(m-\frac{1}{2}\right)\\ & -\left(x_1+\frac{k+t_1}{2}+\frac{t_2+1}{2}\right)\left[m-\left(x_1+\frac{k+t_1}{2}\right)-\frac{t_2+1}{2}\right]\\ & -\left(x_4+\frac{k+t_4}{2}+\frac{t_3+1}{2}\right)\left[m-\left(x_4+\frac{k+t_4}{2}\right)-\frac{t_3+1}{2}\right]\\ & =\sum _{i=2,3}\left(x_i+\frac{k+t_i}{2}\right)\left[m-\left(x_i+\frac{k+t_i}{2}\right)\right]-\left(m-\frac{1}{2}\right)\\ & +\frac{t_2+1}{2}\left(2x_1+k+t_1+\frac{t_2+1}{2}-m\right)+\frac{t_3+1}{2}\left(2x_4+k+t_4+\frac{t_3+1}{2}-m\right)\\ & =\sum _{i=2,3}\left[\left(x_i+\frac{k-1}{2}\right)+\frac{t_i+1}{2}\right]\left[m-\left(x_i+\frac{k-1}{2}\right)-\frac{t_i+1}{2}\right]-\left(m-\frac{1}{2}\right)\\ & +\frac{t_2+1}{2}\left(2x_1+k+t_1+\frac{t_2+1}{2}-m\right)+\frac{t_3+1}{2}\left(2x_4+k+t_4+\frac{t_3+1}{2}-m\right)\\ & =2\left(x_2+\frac{k-1}{2}\right)\left[m-\left(x_2+\frac{k-1}{2}\right)\right]-\left(m-1\right)-\frac{1}{2}+\frac{t_2+1}{2}\left(2t_3-t_1+1\right)\\ & +\frac{t_3+1}{2}\left(2t_2-t_4+1\right)\left(\mathrm{b}\mathrm{e}\mathrm{c}\mathrm{a}\mathrm{u}\mathrm{s}\mathrm{e}{x}_2=x_3,x_1-x_2=t_3-t_1,x_4-x_3=t_2-t_4\right)\\ & >2\cdot \frac{1}{2}\left(x_2+\frac{k-1}{2}\right)\left[m-\left(x_2+\frac{k-1}{2}\right)\right]-\frac{1}{2}+\frac{t_2+1}{2}\left(2t_3-t_1+1\right)\\ & +\frac{t_3+1}{2}\left(2t_2-t_4+1\right)\left(\mathrm{b}\mathrm{y}\mathrm{F}\mathrm{a}\mathrm{c}\mathrm{t}1\right)\\ & >\frac{t_2+1}{2}\left(2t_3+1\right)+\frac{t_3+1}{2}\left(2t_2+1\right)-\frac{1}{2}>0.\end{array}

When k is even(k⩾6), let e_1=v_{\lfloor \frac{k}{2}\rfloor }{v}_{\lfloor \frac{k}{2}\rfloor +1}, E_0=\{u_i{v}_1,e_1\}\subseteq G, E_1=\{u_i{v}_1,e_1\}\subseteq G^{\prime }. In G, let the number of edges near v_1 of u_i{v}_1 and included in E_G\mathrm{\setminus }{E}_{C_k} be b. By comparing G and G^{\prime }, it is easy to know

\begin{array}{rl}{\text{Sz}}_e^{\ast }\left(G\right)-{\text{Sz}}_e^{\ast }\left(G^{\prime }\right)& =\sum _{e=uv\in E_0}\left(m_u\left(e|G\right)+\frac{m_0\left(e|G\right)}{2}\right)\left(m_v\left(e|G\right)+\frac{m_0\left(e|G\right)}{2}\right)\\ & -\sum _{e=uv\in E_1}\left(m_u\left(e|G^{\prime }\right)+\frac{m_0\left(e|G^{\prime }\right)}{2}\right)\left(m_v\left(e|G^{\prime }\right)+\frac{m_0\left(e|G^{\prime }\right)}{2}\right)\\ & =2\left(b+\frac{k}{2}\right)\left[m-\left(b+\frac{k}{2}\right)\right]-2\cdot \frac{1}{2}\left(m-\frac{1}{2}\right)\\ & >0\left(\mathrm{b}\mathrm{y}\mathrm{F}\mathrm{a}\mathrm{c}\mathrm{t}1\right).\end{array}

Repeat the process, if k is odd, then the resulting unicyclic graph has a cycle length of 3. If k is even, then the resulting unicyclic graph has a cycle length of 4.

Next prove the unicyclic graphs with cycle length of 3 or 4, there are no pendant stars at any vertex on the cycle except for u_i and u_{i+1}.

When the length of cycle is 4: Let C_4=u_i{v}_1{v}_2{u}_{i+1}{u}_i. Suppose that at least one of s_{v_1} and s_{v_2} is greater than 0, then move the pendant star from v_1 to u_i, and move the pendant star from v_2 to u_{i+1}. Let the changed graph be G^{\prime }. Let x=m_{u_{i-1}}(e_{i-1}|G)+s_{u_i}+1, y=m_{u_{i+2}}(e_{i+1}|G)+s_{u_{i+1}}+1. Through analysis, it is easy to know

\begin{array}{rl}{\text{Sz}}_e^{\ast }\left(G\right)& -{\text{Sz}}_e^{\ast }\left(G^{\prime }\right)\\ & =\sum _{e=uv\in \{v_1{u}_i,v_2{u}_{i+1}\}}\left(m_u\left(e|G\right)+\frac{m_0\left(e|G\right)}{2}\right)\left(m_v\left(e|G\right)+\frac{m_0\left(e|G\right)}{2}\right)\\ & -\sum _{e=uv\in \{v_1{u}_i,v_2{u}_{i+1}\}}\left(m_u\left(e|G^{\prime }\right)+\frac{m_0\left(e|G^{\prime }\right)}{2}\right)\left(m_v\left(e|G^{\prime }\right)+\frac{m_0\left(e|G^{\prime }\right)}{2}\right)\\ & =2\left(x+y+2\right)\left(s_{v_1}+s_{v_2}+2\right)-4\left(x+y+s_{v_1}+s_{v_2}+2\right)\\ & >0\left(\mathrm{b}\mathrm{y}\mathrm{F}\mathrm{a}\mathrm{c}\mathrm{t}1\right).\end{array}

When the length of cycle is 3: Let C_3=u_i{v}_1{u}_{i+1}{u}_i. Suppose s_{v_1}>0, then move the pendant star from v_1 to u_i. Let the changed graph be G^{\prime }. Let x=m_{u_{i-1}}(e_{i-1}|G)+s_{u_i}+1, y=m_{u_{i+2}}(e_{i+1}|G)+s_{u_{i+1}}+1. Through analysis, it is easy to know

\begin{array}{rl}{\text{Sz}}_e^{\ast }\left(G\right)& -{\text{Sz}}_e^{\ast }\left(G^{\prime }\right)\\ & =\sum _{e=uv\in E_{C_3}}\left(m_u\left(e|G\right)+\frac{m_0\left(e|G\right)}{2}\right)\left(m_v\left(e|G\right)+\frac{m_0\left(e|G\right)}{2}\right)\\ & -\sum _{e=uv\in E_{C_3}}\left(m_u\left(e|G^{\prime }\right)+\frac{m_0\left(e|G^{\prime }\right)}{2}\right)\left(m_v\left(e|G^{\prime }\right)+\frac{m_0\left(e|G^{\prime }\right)}{2}\right)\\ & =\left(x+\frac{s_{v_1}+3}{2}\right)\left(y+\frac{3}{2}+\frac{s_{v_1}}{2}\right)-\left(x+\frac{s_{v_1}+3}{2}+\frac{s_{v_1}}{2}\right)\left(y+\frac{3}{2}\right)\\ & +\left(\frac{x}{2}+\frac{s_{v_1}+3}{2}+\frac{s_{v_1}}{2}\right)\left(\frac{x}{2}+y+\frac{3}{2}\right)-\left(\frac{x}{2}+\frac{s_{v_1}+3}{2}\right)\left(\frac{x}{2}+y+\frac{3}{2}+\frac{s_{v_1}}{2}\right)\end{array}

\begin{array}{rl}& +\left(x+\frac{y}{2}+\frac{3}{2}\right)\left(\frac{y}{2}+\frac{3}{2}+s_{v_1}\right)-\left(x+\frac{y}{2}+\frac{3}{2}+s_{v_1}\right)\left(\frac{y}{2}+\frac{3}{2}\right)\\ & =\frac{s_{v_1}}{2}\left(x-y+\frac{s_{v_1}}{2}\right)+\frac{s_{v_1}}{2}\left(y-\frac{s_{v_1}}{2}\right)+s_{v_1}\cdot x\\ & =\frac{3}{2}{s}_{v_1}\cdot x>0.\end{array}

Next prove that there is no pendant star at any vertex on P_{d+1} except u_i.

For convenience, let x=m_{u_{i-1}}(e_{i-1}|G)+1, y=m_{u_{i+2}}(e_{i+1}|G)+1. Without loss of generality, suppose x⩾y, we first prove that under the premise of x⩾y, if s_{u_i}+s_{u_{i+1}}>0, then only s_{u_i} is greater than 0 for x>y, either s_{u_i} or s_{u_{i+1}} is greater than 0 for x=y.

If x>y, suppose s_{u_{i+1}}>0, then move the pendant star on u_{i+1} to u_i. Let the changed graph be G^{\prime }.

If the length of cycle is 4, then

\begin{array}{rl}{\text{Sz}}_e^{\ast }(G)-{\text{Sz}}_e^{\ast }(G^{\prime })& =2(x+s_{u_i}+2)(y+s_{u_{i+1}}+2)-2(x+s_{u_i}+s_{u_{i+1}}+2)(y+2)\\ & =2s_{u_{i+1}}(x+s_{u_i}+2)-2s_{u_{i+1}}(y+2)\\ & =2s_{u_{i+1}}(x-y+s_{u_i})>0.\end{array}

If the length of cycle is 3, then

\begin{array}{rl}{\text{Sz}}_e^{\ast }\left(G\right)& -{\text{Sz}}_e^{\ast }\left(G^{\prime }\right)\\ & =\left(x+s_{u_i}+\frac{3}{2}\right)\left(y+s_{u_{i+1}}+\frac{3}{2}\right)-\left(x+s_{u_i}+s_{u_{i+1}}+\frac{3}{2}\right)\left(y+\frac{3}{2}\right)\\ & +\left(x+s_{u_i}+1+\frac{y+s_{u_{i+1}}+1}{2}\right)\left(1+\frac{y+s_{u_{i+1}}+1}{2}\right)\\ & -\left(x+s_{u_i}+s_{u_{i+1}}+1+\frac{y+1}{2}\right)\left(1+\frac{y+1}{2}\right)\\ & +\left(1+\frac{x+s_{u_i}+1}{2}\right)\left(y+s_{u_{i+1}}+1+\frac{x+s_{u_i}+1}{2}\right)\\ & -\left(1+\frac{x+s_{u_i}+s_{u_{i+1}}+1}{2}\right)\left(y+1+\frac{x+s_{u_i}+s_{u_{i+1}}+1}{2}\right)\\ & =\left(x+s_{u_i}+\frac{3}{2}\right)\left[\left(y+\frac{3}{2}\right)+s_{u_{i+1}}\right]-\left[\left(x+s_{u_i}+\frac{3}{2}\right)+s_{u_{i+1}}\right]\left(y+\frac{3}{2}\right)\\ & +\left(x+s_{u_i}+\frac{y+s_{u_{i+1}}+3}{2}\right)\left[\left(\frac{y+3}{2}\right)+\frac{s_{u_{i+1}}}{2}\right]\\ & -\left[\left(x+s_{u_i}+\frac{y+s_{u_{i+1}}+3}{2}\right)+\frac{s_{u_{i+1}}}{2}\right]\left(\frac{y+3}{2}\right)\\ & +\left(\frac{x+s_{u_i}+3}{2}\right)\left[\left(y+\frac{x+s_{u_i}+s_{u_{i+1}}+3}{2}\right)+\frac{s_{u_{i+1}}}{2}\right]\\ & -\left[\left(\frac{x+s_{u_i}+3}{2}\right)+\frac{s_{u_{i+1}}}{2}\right]\left(y+\frac{x+s_{u_i}+s_{u_{i+1}}+3}{2}\right)\end{array}

=\frac{3s_{u_{i+1}}}{2}\left(x-y+s_{u_i}\right)>0.

If x=y, suppose s_{u_i}{s}_{u_{i+1}}>0, then move the pendant star from u_{i+1} to u_i. Let the changed graph be G^{\prime }.

If the length of cycle is 4, then similarly,

\begin{array}{l}{\text{Sz}}_e^{\ast }(G)-{\text{Sz}}_e^{\ast }(G^{\prime })=2s_{u_{i+1}}(x-y+s_{u_i})=2s_{u_i}{s}_{u_{i+1}}>0\end{array}

If the length of cycle is 3, then similarly,

{\text{Sz}}_e^{\ast }(G)-{\text{Sz}}_e^{\ast }(G^{\prime })=\frac{3s_{u_{i+1}}}{2}(x-y+s_{u_i})=\frac{3}{2}{s}_{u_i}{s}_{u_{i+1}}>0.

Next prove that there is no pendant star at any vertex on P_{d+1} except u_i and u_{i+1}. Otherwise, suppose a pendant star exists at u_r, without loss of generality, let , and then prove it in two cases:

(i) m_{u_r}(e_r|G)⩽m_{u_{r+1}}(e_r|G). Move the pendant star from u_r to u_{r+1}. Let the changed graph be G^{\prime }. Hence,

\begin{array}{rl}{\text{Sz}}_e^{\ast }\left(G\right)-{\text{Sz}}_e^{\ast }\left(G^{\prime }\right)& =\left(m_{u_r}\left(e_r|G\right)+\frac{1}{2}\right)\left(m_{u_{r+1}}\left(e_r|G\right)+\frac{1}{2}\right)\\ & -\left(m_{u_r}\left(e_r|G\right)-s_{u_r}+\frac{1}{2}\right)\left(m_{u_{r+1}}\left(e_r|G\right)+s_{u_r}+\frac{1}{2}\right)\\ & >0\left(\mathrm{b}\mathrm{y}\mathrm{F}\mathrm{a}\mathrm{c}\mathrm{t}1\right).\end{array}

(ii) m_{u_r}(e_r|G)>m_{u_{r+1}}(e_r|G). When the length of cycle is 4: delete v_1{u}_i, v_2{u}_{i+1}, add v_1{u}_{i-1}, v_2{u}_i, move the pendant star from u_i to u_{i-1}. Let the changed graph be G^{″}. Hence,

\begin{array}{rl}{\text{Sz}}_e^{\ast }\left(G\right)-{\text{Sz}}_e^{\ast }\left(G^{″}\right)& =\left(x-\frac{1}{2}\right)\left(y+\frac{1}{2}+s_{u_i}+4\right)+2\left(x+s_{u_i}+2\right)\left(y+2\right)\\ & -\left(y+\frac{1}{2}\right)\left(x+s_{u_i}+\frac{7}{2}\right)-2\left(x+s_{u_i}+1\right)\left(y+3\right)\\ & =\left(x-\frac{1}{2}\right)\left(s_{u_i}+4\right)-\left(y+\frac{1}{2}\right)\left(s_{u_i}+4\right)-2\left(x-y+s_{u_i}-1\right)\\ & =\left(x-y-1\right)\left(s_{u_i}+4\right)-2\left(x-y+s_{u_i}-1\right)\\ & =\left(x-y\right)\left(s_{u_i}+2\right)-\left(3s_{u_i}+2\right).\end{array}

Here, x=m_{u_{i-1}}(e_{i-1}|G)+1⩾m_{u_r}(e_r|G)+1, y=m_{u_{i+2}}(e_{i+1}|G)+1⩽m_{u_{r+1}}(e_r|G)-4. We have x-y⩾m_{v_r}(e_r|G)+1-m_{v_{r+1}}(e_r|G)+4>5, so {\text{Sz}}_e^{\ast }(G)-{\text{Sz}}_e^{\ast }(G^{″})>0.

When the length of cycle is 3: delete v_1{u}_{i+1}, add v_1{u}_{i-1}, move the pendant star from u_i to u_{i-1}. Let the changed graph be G^{″}. Hence,

\begin{array}{rl}{\text{Sz}}_e^{\ast }\left(G\right)& -{\text{Sz}}_e^{\ast }\left(G^{‴}\right)\\ & =\left(x-1+\frac{1}{2}\right)\left(y+s_{u_i}+3+\frac{1}{2}\right)-\left(x+s_{u_i}+2+\frac{1}{2}\right)\left(y+\frac{1}{2}\right)\\ & +\left(x+s_{u_i}+1+\frac{1}{2}\right)\left(y+1+\frac{1}{2}\right)-\left(x+s_{u_i}+\frac{1}{2}\right)\left(y+2+\frac{1}{2}\right)\\ & +\left(1+\frac{x+s_{u_i}+1}{2}\right)\left(y+1+\frac{x+s_{u_i}+1}{2}\right)\\ & -\left(1+\frac{x+s_{u_i}}{2}\right)\left(y+2+\frac{x+s_{u_i}}{2}\right)+\left(x+s_{u_i}+1+\frac{y+1}{2}\right)\left(1+\frac{y+1}{2}\right)\\ & -\left(x+s_{u_i}+\frac{y+2}{2}\right)\left(1+\frac{y+2}{2}\right)\\ & =\left(x-\frac{1}{2}\right)\left[\left(y+\frac{1}{2}\right)+s_{u_i}+3\right]-\left[\left(x-\frac{1}{2}\right)+s_{u_i}+3\right]\left(y+\frac{1}{2}\right)\\ & +\left[\left(x+s_{u_i}+\frac{1}{2}\right)+1\right]\left(y+\frac{3}{2}\right)-\left(x+s_{u_i}+\frac{1}{2}\right)\left[\left(y+\frac{3}{2}\right)+1\right]\\ & +\left[\left(\frac{x+s_{u_i}+2}{2}\right)+\frac{1}{2}\right]\left(y+\frac{x+s_{u_i}+3}{2}\right)\\ & -\left(\frac{x+s_{u_i}+2}{2}\right)\left[\left(y+\frac{x+s_{u_i}+3}{2}\right)+\frac{1}{2}\right]\\ & +\left[\left(x+s_{u_i}+\frac{y+2}{2}\right)+\frac{1}{2}\right]\left(\frac{y+3}{2}\right)\\ & -\left(x+s_{u_i}+\frac{y+2}{2}\right)\left[\left(\frac{y+3}{2}\right)+\frac{1}{2}\right]\\ & =\left(x-y\right)\left(s_{u_i}+\frac{3}{2}\right)-\left(\frac{5}{2}{s}_{u_i}+\frac{3}{2}\right).\end{array}

Here, x=m_{u_{i-1}}(e_{i-1}|G)+1⩾m_{u_r}(e_r|G)+1, y=m_{u_{i+2}}(e_{i+1}|G)+1⩽m_{u_{r+1}}(e_r|G)-3. We have x-y⩾m_{v_r}(e_r|G)+1-m_{v_{r+1}}(e_r|G)+3>4, so {\text{Sz}}_e^{\ast }(G)-{\text{Sz}}_e^{\ast }(G^{‴})>0.

Now G is an unicyclic graph satisfying that the length of cycle is 3 or 4, and there is no pendant star at any vertex except u_i.

Next prove that when m⩾20, the revised edge-Szeged index of the cycle length 4 is smaller than that of the unicyclic graph with cycle length 3.

For a unicyclic graph with a cycle length of 4, let x=m_{u_{i-1}}(e_{i-1}|G)+s_{u_i}+1, y=m_{u_{i+2}}(e_{i+1}|G)+1, so we have x+y=m-4. Suppose x⩾y⩾1, we make the following changes: delete v_1{v}_2, add v_2{u}_i, let the changed graph as G^{″}. Through analysis, it is easy to know

\begin{array}{rl}& {\text{Sz}}_e^{\ast }\left(G\right)-{\text{Sz}}_e^{\ast }\left(G^{\prime }\right)\\ & =\sum _{e=uv\in E_{C_4}}\left(m_u\left(e|G\right)+\frac{m_0\left(e|G\right)}{2}\right)\left(m_v\left(e|G\right)+\frac{m_0\left(e|G\right)}{2}\right)\end{array}

\begin{array}{rl}& -\sum _{e=uv\in E_{C_3}\bigcup \{v_1{u}_i\}}\left(m_u\left(e|G^{\prime }\right)+\frac{m_0\left(e|G^{\prime }\right)}{2}\right)\left(m_v\left(e|G^{\prime }\right)+\frac{m_0\left(e|G^{\prime }\right)}{2}\right)\\ & =2\left(x+2\right)\left(y+2\right)+2\cdot 2\left(x+y+2\right)-\frac{1}{2}\left(x+y+\frac{7}{2}\right)\\ & -\left(x+\frac{5}{2}\right)\left(y+\frac{3}{2}\right)-\left(\frac{x}{2}+2\right)\left(\frac{x}{2}+y+2\right)-\left(\frac{y}{2}+\frac{3}{2}\right)\left(x+\frac{y}{2}+\frac{5}{2}\right)\\ & =-\frac{x^2}{4}-\frac{y^2}{4}+\frac{5}{2}x+y+\frac{11}{4}\\ & =-\frac{1}{4}(x^2+y^2-10x-4y)+\frac{11}{4}\\ & =-\frac{1}{4}(x-5{)}^2-\frac{1}{4}(y-2{)}^2+10.\end{array}

Because of x⩾y⩾1, for to be true, as long as x⩾12, when y=1; x⩾12, when y=2; x⩾12, when y=3; x⩾12, when y=4; x⩾11, when y=5; x⩾10, when y=6; x⩾9, when y=7; x⩾8, when y=8; x⩾y, when y>1. And because of x+y=m-4, m=x+y+4⩾20.

Finally prove that for 0⩽s_{u_i}⩽1, u_i coincides with u_{\lfloor \frac{d}{2}\rfloor }; for s_{u_i}=2, u_i coincides with u_{\lfloor \frac{d}{2}\rfloor } or u_{\lceil \frac{d}{2}\rceil }, for s_{u_i}⩾3, u_i coincides with u_{\lceil \frac{d}{2}\rceil }. Without loss of generality, suppose , then delete v_1{u}_i and v_2{u}_{i+1}, add v_1{u}_{i+1} and v_2{u}_{i+2}, move the pendant star from u_i to u_{i+1}. Let the changed graph be G^{\prime }. For convenience, let x=m_{u_{i-1}}(e_{i-1}|G)+1, y=m_{u_{i+2}}(e_{i+1}|G)+1. So

\begin{array}{rl}{\text{Sz}}_e^{\ast }\left(G\right)& -{\text{Sz}}_e^{\ast }\left(G^{\prime }\right)\\ & =2\left(x+s_{u_i}+2\right)\left(y+2\right)+\left(x+s_{u_i}+4+\frac{1}{2}\right)\left(y-\frac{1}{2}\right)\\ & -\left(x+\frac{1}{2}\right)\left(y+s_{u_i}+3+\frac{1}{2}\right)-2\left(x+s_{u_i}+3\right)\left(y+1\right)\\ & =2\left(x+s_{u_i}+2\right)\left[\left(y+1\right)+1\right]+\left[\left(x+\frac{1}{2}\right)+s_{u_i}+4\right]\left(y-\frac{1}{2}\right)\\ & -\left(x+\frac{1}{2}\right)\left[\left(y-\frac{1}{2}\right)+s_{u_i}+4\right]-2\left[\left(x+s_{u_i}+2\right)+1\right]\left(y+1\right)\\ & =2\left(x+s_{u_i}+2\right)+\left(y-\frac{1}{2}\right)\left(s_{u_i}+4\right)-\left(x+\frac{1}{2}\right)\left(s_{u_i}+4\right)-2\left(y+1\right)\\ & =2\left(x-y+s_{u_i}+1\right)+\left(y-x-1\right)\left(s_{u_i}+4\right)\\ & =\left(y-x\right)\left(s_{u_i}+2\right)+s_{u_i}-2.\end{array}

Known , so i⩽\lceil \frac{d}{2}\rceil -1. If d is odd, then i⩽\frac{d+1}{2}-1, 2i⩽d-1. If d is even, then i⩽\frac{d}{2}-1, 2i⩽d-2. Since y-x=(d-i-1)-i=d-2i-1, y-x⩾d-(d-1)-1=0. If y-x=0, then {\text{Sz}}_e^{\ast }(G)-{\text{Sz}}_e^{\ast }(G^{\prime })=s_{u_i}-2. If y-x=1, then {\text{Sz}}_e^{\ast }(G)-{\text{Sz}}_e^{\ast }(G^{\prime })=2s_{u_i}. If y-x⩾2, then {\text{Sz}}_e^{\ast }(G)-{\text{Sz}}_e^{\ast }(G^{\prime })=(y-x)(s_{u_i}+2)+s_{u_i}-2>0.

So, if 0⩽s_{u_i}⩽1, then G_2 in Fig.3 is the corresponding graph attained the minimum revised edge-Szeged index, and

{\text{Sz}}_e^{\ast }(G_2)=\{\begin{array}{r}\frac{(d^2+2m+22)m}{4}-\frac{d^3+3d^2+35d+141}{12},d\mathrm{i}\mathrm{s}\mathrm{o}\mathrm{d}\mathrm{d};\\ \frac{(d^2+2m+19)m}{4}-\frac{d^3+3d^2+26d+108}{12},d\mathrm{i}\mathrm{s}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n}.\end{array}

If s_{u_i}⩾3, G_3 in Fig.3 is the corresponding graph attained the minimum revised edge-Szeged index, and

{\text{Sz}}_e^{\ast }(G_3)=\{\begin{array}{r}\frac{(d^2+2m+18)m}{4}-\frac{d^3+3d^2+23d+81}{12},d\mathrm{i}\mathrm{s}\mathrm{o}\mathrm{d}\mathrm{d};\\ \frac{(d^2+2m+19)m}{4}-\frac{d^3+3d^2+26d+108}{12},d\mathrm{i}\mathrm{s}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n}.\end{array}

If s_{u_i}=2, then {\text{Sz}}_e^{\ast }(G_2)={\text{Sz}}_e^{\ast }(G_3).

(2) Next, consider |V_{P_{d+1}}\bigcap V_{C_k}|=3, k=4. In this case, let V_{C_4}=u_i{v}_1{u}_{i+2}{u}_{i+1}{u}_i, V_{P_{d+1}}\bigcap V_{C_4}=\{u_i,u_{i+1},u_{i+2}\}. For convenience, let the number of pendant stars on u_i,u_{i+1},u_{i+2},v_1 be s_0,s_1,s_2,s_3, respectively. Let x=m_{u_{i-1}}(e_{i-1}|G)+1, y=m_{u_{i+3}}(e_{i+2}|G)+1. Without loss of generality, suppose x⩾y, s_1+s_2+s_3>0, we make the following changes for G: move the pendant star from v_1 to u_{i+1}(s_1{s}_3>0), move the pendant star from u_{i+2} to u_i(s_2>0), let the changed graph be G^{\prime }. Hence

\begin{array}{rl}{\text{Sz}}_e^{\ast }\left(G\right)& -{\text{Sz}}_e^{\ast }\left(G^{\prime }\right)\\ & =\sum _{e=uv\in E_{C_4}}\left(m_u\left(e|G\right)+\frac{m_0\left(e|G\right)}{2}\right)\left(m_v\left(e|G\right)+\frac{m_0\left(e|G\right)}{2}\right)\\ & -\sum _{e=uv\in E_{C_4}}\left(m_u\left(e|G^{\prime }\right)+\frac{m_0\left(e|G^{\prime }\right)}{2}\right)\left(m_v\left(e|G^{\prime }\right)+\frac{m_0\left(e|G^{\prime }\right)}{2}\right)\\ & =2\left(x+s_0+s_3+2\right)\left(y+s_1+s_2+2\right)+2\left(x+s_0+s_1+2\right)\left(y+s_2+s_3+2\right)\\ & -2\left(x+s_0+s_2+2\right)\left(y+s_1+s_3+2\right)\\ & -2\left(x+s_0+s_1+s_2+s_3+2\right)\left(y+2\right)\\ & =2[\left(x+s_0+2\right)+s_3][\left(y+s_1+2\right)+s_2]\\ & +2\left(x+s_0+s_1+2\right)[\left(y+2\right)+s_2+s_3]\end{array}

\begin{array}{rl}& -2[\left(x+s_0+2\right)+s_2][\left(y+s_1+2\right)+s_3]\\ & -2[\left(x+s_0+s_1+2\right)+s_2+s_3]\left(y+2\right)\\ & =2s_2\left(x-y+s_0-s_1-s_3\right)+2s_3\left(y-x+s_1+s_2-s_0\right)\\ & +2\left(s_2+s_3\right)\left(x-y+s_0+s_1\right)\\ & =4s_2\left(x-y\right)+4s_0{s}_2+4s_1{s}_3\\ & >0.\end{array}

Based on this, move the pendant star from u_{i+1} to u_i, let the changed graph be G^{″}. For convenience, record the number of edges of the pendant star on u_i,u_{i+1} in G^{\prime } as s_a,s_b(s_b>0), respectively.

\begin{array}{rl}{\text{Sz}}_e^{\ast }\left(G^{\prime }\right)-{\text{Sz}}_e^{\ast }\left(G^{″}\right)& =\sum _{e=uv\in E_{C_4}}\left(m_u\left(e|G^{\prime }\right)+\frac{m_0\left(e|G^{\prime }\right)}{2}\right)\left(m_v\left(e|G^{\prime }\right)+\frac{m_0\left(e|G^{\prime }\right)}{2}\right)\\ & -\sum _{e=uv\in E_{C_4}}\left(m_u\left(e|G^{″}\right)+\frac{m_0\left(e|G^{″}\right)}{2}\right)\left(m_v\left(e|G^{″}\right)+\frac{m_0\left(e|G^{″}\right)}{2}\right)\\ & =2\left(x+s_a+2\right)\left(y+s_b+2\right)+2\left(x+s_a+s_b+2\right)\left(y+2\right)\\ & -4\left(x+s_a+s_b+2\right)\left(y+2\right)\\ & =2\left(x+s_a+2\right)\left(y+2+s_b\right)-2\left(x+s_a+2+s_b\right)\left(y+2\right)\\ & =2s_b\left(x-y+s_a\right)\\ & ⩾0,\end{array}

with equality if and only if x=y and s_a=0.

In summary, in order to make the revised edge-Szeged index of unicyclic graph with given diameter smaller, it can be considered that there are no pendant stars except for u_i on the cycle.

Then it is proved that there is no pendant star on P_{d+1} except u_i. Otherwise, without loss of generality, assuming there is a pendant star at u_r on P_{d+1}, where . Next, we will discuss two cases:

(i) m_{u_r}(e_r|G)⩽m_{u_{r+1}}(e_r|G). Move the pendant star from u_r to u_{r+1}, let the changed graph be G^{\prime }. Then comparing G and G^{\prime }, it was found that for all e=uv\in E_G\mathrm{\setminus }{e}_r, we have m_u(e|G)=m_u(e|G^{\prime }), m_v(e|G)=m_v(e|G^{\prime }), m_0(e|G)=m_0(e|G^{\prime }). Therefore

\begin{array}{rl}{\text{Sz}}_e^{\ast }\left(G\right)-{\text{Sz}}_e^{\ast }\left(G^{\prime }\right)& =\left(m_{u_r}\left(e_r|G\right)+\frac{1}{2}\right)\left(m_{u_{r+1}}\left(e_r|G\right)+\frac{1}{2}\right)\\ & -\left(m_{u_r}\left(e_r|G\right)-s_{u_r}+\frac{1}{2}\right)\left(m_{u_{r+1}}\left(e_r|G\right)+s_{u_r}+\frac{1}{2}\right)\\ & >0\left(\mathrm{b}\mathrm{y}\mathrm{F}\mathrm{a}\mathrm{c}\mathrm{t}1\right).\end{array}

(ii) m_{u_r}(e_r|G)>m_{u_{r+1}}(e_r|G). First, delete v_1{u}_{i-1} and v_1{u}_{i+1}, add v_1{u}_{i-1} and v_1{u}_{i+1}, and then move the pendant star from u_i to u_{i-1}, let the changed graph be G^{″}. Let E_0=\{v_1{u}_i,v_1{u}_{i+2},e_{i-1},e_i,e_{i+1}\}\subseteq G, E_1=\{v_1{u}_{i-1},v_1{u}_{i+1}, e_{i-1},e_i,e_{i+1}\}\subseteq G^{″}. Comparing G and G^{\prime }, it is easy to know

\begin{array}{rl}{\text{Sz}}_e^{\ast }\left(G\right)-{\text{Sz}}_e^{\ast }\left(G^{″}\right)& =\sum _{e=uv\in E_0}\left(m_u\left(e|G\right)+\frac{m_0\left(e|G\right)}{2}\right)\left(m_v\left(e|G\right)+\frac{m_0\left(e|G\right)}{2}\right)\\ & -\sum _{e=uv\in E_1}\left(m_u\left(e|G^{″}\right)+\frac{m_0\left(e|G^{″}\right)}{2}\right)\left(m_v\left(e|G^{″}\right)+\frac{m_0\left(e|G^{″}\right)}{2}\right)\\ & =4\left(x+s_{u_i}+2\right)\left(y+2\right)+\left(x-\frac{1}{2}\right)\left(y+s_{u_i}+4+\frac{1}{2}\right)\\ & -4\left(x+s_{u_i}+1\right)\left(y+3\right)-\left(x+s_{u_i}+3+\frac{1}{2}\right)\left(y+\frac{1}{2}\right)\\ & =4\left[\left(x+s_{u_i}+1\right)+1\right]\left(y+2\right)+\left(x-\frac{1}{2}\right)\left[\left(y+\frac{1}{2}\right)+s_{u_i}+4\right]\\ & -4\left(x+s_{u_i}+1\right)\left[\left(y+2\right)+1\right]-\left[\left(x-\frac{1}{2}\right)+s_{u_i}+4\right]\left(y+\frac{1}{2}\right)\\ & =4\left(y-x-s_{u_i}+1\right)+\left(x-y-1\right)\left(s_{u_i}+4\right)\\ & =\left(x-y-5\right)s_{u_i}.\end{array}

Because x=m_{u_{i-1}}(e_{i-1}|G)+1⩾m_{u_r}(e_r|G)+1, y=m_{u_{i+3}}(e_{i+2}|G)+1⩽ m_{v_{r+1}}(e_r|G)-4. So, x-y⩾m_{v_r}(e_r|G)+1-m_{v_{r+1}}(e_r|G)+4>5. Therefore, {\text{Sz}}_e^{\ast }(G)-{\text{Sz}}_e^{\ast }(G^{″})⩾0, with equality if and only if s_{u_i}=0. Continue this process until all pendant stars on P_{d+1} move to u_i.

Finally, it is proved that for d⩾6, u_i coincides with u_{\lceil \frac{d}{2}\rceil +1}. Otherwise, without loss of generality, suppose , then delete v_1{u}_i and v_1{u}_{i+2}, add v_1{u}_{i+1}, and v_1{u}_{i+3}, move the pendant star from u_i to u_{i+1}, let the changed graph be G^{\prime }. Then

\begin{array}{rl}{\text{Sz}}_e^{\ast }(G)-{\text{Sz}}_e^{\ast }(G^{\prime })& =4(x+s_{u_i}+2)(y+2)+\left(x+s_{u_i}+4+\frac{1}{2}\right)\left(y-\frac{1}{2}\right)\\ & -4(x+s_{u_i}+3)(y+1)-\left(x+\frac{1}{2}\right)\left(y+s_{u_i}+3+\frac{1}{2}\right)\\ & =4(x+s_{u_i}+2)[(y+1)+1]+\left[\left(x+\frac{1}{2}\right)+s_{u_i}+4\right]\left(y-\frac{1}{2}\right)\\ & -4[(x+s_{u_i}+2)+1](y+1)-[\left(x+\frac{1}{2}\right)\left[\left(y+\frac{1}{2}\right)+s_{u_i}+4\right]\\ & =(y-x+3)s_{u_i}.\end{array}

Known , so i⩽\lceil \frac{d}{2}\rceil. If d is odd, then i⩽\frac{d+1}{2}, 2i⩽d+1. If d is even, then i⩽\frac{d}{2}, 2i⩽d. Since y-x=(d-i-2)-i=d-2i-2, y-x⩾d-(d+1)-2=-3. So {\text{Sz}}_e^{\ast }(G)-{\text{Sz}}_e^{\ast }(G^{\prime })⩾0, with equality if and only if d is odd and u_i coincides with u_{\lceil \frac{d}{2}\rceil } or s_{u_i}=0. So far, the obtained graph is shown in G_4 of Fig.4, this graph is also the corresponding graph attained the minimum revised edge-Szeged index for |V_{P_{d+1}}\bigcap V_{C_k}|=3, k=4, and

{\text{Sz}}_e^{\ast }(G_4)=\{\begin{array}{rl}& \frac{(d^2+2m+2d)m}{4}-\frac{d^3+6d^2+11d-54}{12},(d\mathrm{i}\mathrm{s}\mathrm{o}\mathrm{d}\mathrm{d});\\ & \frac{(d^2+2m+2d-1)m}{4}-\frac{d^3+6d^2+8d-60}{12},(d\mathrm{i}\mathrm{s}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n}).\end{array}

Here, due to \lceil \frac{d}{2}\rceil +3⩽d, for d is odd, it needs to satisfy d⩾7, and for d is even, it needs to satisfy d⩾6.

For 3⩽d⩽5, u_i coincides with u_{d-2}. Otherwise, just like the above method, suppose , then delete v_1{u}_i and v_1{u}_{i+2}, add v_1{u}_{i+1} and v_1{u}_{i+3}, move the pendant star from u_i to u_{i+1}, let the changed graph be G^{\prime }. Then {\text{Sz}}_e^{\ast }(G)-{\text{Sz}}_e^{\ast }(G^{\prime })=(y-x+3)s_{u_i}⩾0, with equality if and only if s_{u_i}=0. Therefore, when u_i and u_{d-2} are coinciding, the revised edge-Szeged index of such unicyclic graphs is the smallest (see G_5 in Fig.4 for specific graphs), and

{\text{Sz}}_e^{\ast }(G_5)=\frac{(2d^2+2m-10d+35)m}{4}-\frac{d^3-6d^2+11d+39}{3}.

(3) Finally, consider |V_{P_{d+1}}\bigcap V_{C_k}|⩾3, k⩾5. Let V_{P_{d+1}}\bigcap V_{C_k}=\{u_i,u_{i+1},\dots, u_{i+t}\}(2⩽t⩽\lfloor \frac{k}{2}\rfloor ), C_k=u_i{v}_1\cdots v_{k-t-1}{u}_{i+t}{u}_{i+t-1}\cdots u_{i+1}{u}_i. Let x=m_{u_{i-1}}(e_{i-1}|G)+1, y=m_{u_{i+t+1}}(e_{i+t}|G)+1. Without loss of generality, suppose x⩽y, we make the following changes for G: contracting v_{\lfloor \frac{k-2}{2}\rfloor }{v}_{\lfloor \frac{k-2}{2}\rfloor +1} to v_{\lfloor \frac{k-2}{2}\rfloor }, add pendant edge v_{\lfloor \frac{k-2}{2}\rfloor }{v}_{\lfloor \frac{k-2}{2}\rfloor +1} in v_{\lfloor \frac{k-2}{2}\rfloor }, delete u_i{v}_1, add u_{i+1}{v}_1, move the pendant star from u_i to u_{i+1}, let the changed graph be G^{\prime }. Let P_1=u_i{v}_1{v}_2\cdots v_{\lfloor \frac{k-2}{2}\rfloor -1}{v}_{\lfloor \frac{k-2}{2}\rfloor }, P_2=u_{i+1}{u}_{i+2}\cdots u_{i+t}{v}_{k-t-1}\cdots v_{\lfloor \frac{k-2}{2}\rfloor +1}. Let e_1=v_{\lfloor \frac{k-2}{2}\rfloor }{v}_{\lfloor \frac{k-2}{2}\rfloor +1}, e_2=v_{\lfloor \frac{k-2}{2}\rfloor +1}{v}_{\lfloor \frac{k-2}{2}\rfloor +2}, e_3=v_{\lfloor \frac{k-2}{2}\rfloor }{v}_{\lfloor \frac{k-2}{2}\rfloor +2}.

When k is even(k⩾6), it is easy to know

\begin{array}{rl}& \sum _{e=uv\in E_G\mathrm{\setminus }\{v_1{u}_i,e_i,e_1,e_2\}}\left(m_u\left(e|G\right)+\frac{m_0\left(e|G\right)}{2}\right)\left(m_v\left(e|G\right)+\frac{m_0\left(e|G\right)}{2}\right)\\ & =\sum _{e=uv\in E_{G^{\prime }}\mathrm{\setminus }\{v_1{u}_{i+1},e_i,e_1,e_3\}}\left(m_u\left(e|G^{\prime }\right)+\frac{m_0\left(e|G^{\prime }\right)}{2}\right)\left(m_v\left(e|G^{\prime }\right)+\frac{m_0\left(e|G^{\prime }\right)}{2}\right).\end{array}

And because the revised edge-Szeged index of v_1{u}_i(e_2) in G corresponds to the same as that of v_1{u}_{i+1}(e_3) in G^{\prime }. So

\begin{array}{rl}{\text{Sz}}_e^{\ast }\left(G\right)& -{\text{Sz}}_e^{\ast }\left(G^{\prime }\right)\\ & =\sum _{e=uv\in \{e_i,e_1\}}\left(m_u\left(e|G\right)+\frac{m_0\left(e|G\right)}{2}\right)\left(m_v\left(e|G\right)+\frac{m_0\left(e|G\right)}{2}\right)\\ & -\sum _{e=uv\in \{e_i,e_1\}}\left(m_u\left(e|G^{\prime }\right)+\frac{m_0\left(e|G^{\prime }\right)}{2}\right)\left(m_v\left(e|G^{\prime }\right)+\frac{m_0\left(e|G^{\prime }\right)}{2}\right)\\ & =2\left(x+\sum _{u\in V_{P_1}}{s}_u+\frac{k}{2}\right)\left(y+\sum _{v\in V_{P_2}}{s}_v+\frac{k}{2}\right)\\ & -\frac{1}{2}\left(x+y+\sum _{w\in V_{P_1}\bigcup V_{P_2}}{s}_w+k-\frac{1}{2}\right)\\ & -\left(x+\frac{1}{2}\right)\left(y+\sum _{w\in V_{P_1}\bigcup V_{P_2}}{s}_w+k-\frac{1}{2}\right)\\ & >0\left(\mathrm{b}\mathrm{y}\mathrm{F}\mathrm{a}\mathrm{c}\mathrm{t}1\right).\end{array}

When k is odd(k⩾5), Let E_0=\{e_i,e_{i+1},e_1,e_2\}\subseteq G, E_1=\{e_i,e_{i+1},e_1,e_3\}\subseteq G^{\prime }. For convenience, let the pendant star on v_{\lfloor \frac{k-2}{2}\rfloor } be S_1, the pendant star on v_{\lfloor \frac{k-2}{2}\rfloor +1} be S_2. Through analysis, it is easy to know

\begin{array}{rl}& \sum _{e=uv\in E_G\mathrm{\setminus }{E}_0}\left(m_u\left(e|G\right)+\frac{m_0\left(e|G\right)}{2}\right)\left(m_v\left(e|G\right)+\frac{m_0\left(e|G\right)}{2}\right)\\ & =\sum _{e=uv\in E_{G^{\prime }}\mathrm{\setminus }{E}_1}\left(m_u\left(e|G^{\prime }\right)+\frac{m_0\left(e|G^{\prime }\right)}{2}\right)\left(m_v\left(e|G^{\prime }\right)+\frac{m_0\left(e|G^{\prime }\right)}{2}\right).\end{array}

Next, compare the revised edge-Szeged index of e_i,e_{i+1},e_1,e_2 in G and e_i,e_{i+1},e_1, e_3 in G^{\prime }. According to the above four edges, the difference of the revised edge-Szeged index is denoted as L_1, L_2, L_3, L_4, respectively. Then

\begin{array}{rl}{L}_1& =\left(x+\sum _{u\in V_{P_1}}{s}_u+\frac{k-1}{2}+\frac{s_2+1}{2}\right)\left(y+\sum _{v\in V_{P_2}}{s}_v-s_2+\frac{k-1}{2}+\frac{s_2+1}{2}\right)\\ & -\left(x+\frac{1}{2}\right)\left(y+\sum _{w\in V_{P_1}\bigcup V_{p_2}}{s}_w+k-2+1+\frac{1}{2}\right)\\ & =\left(x+\sum _{u\in V_{P_1}}{s}_u+\frac{k+s_2}{2}\right)\left(y+\sum _{v\in V_{P_2}}{s}_v+\frac{k-s_2}{2}\right)\\ & -\left(x+\frac{1}{2}\right)\left(y+\sum _{w\in V_{P_1}\bigcup V_{P_2}}{s}_w+k-\frac{1}{2}\right)\end{array}

\begin{array}{rl}& =\left(-\sum _{u\in V_{P_1}}{s}_u-\frac{k+s_2-1}{2}\right)x+\left(\sum _{u\in V_{P_1}}{s}_u+\frac{k+s_2-1}{2}\right)y\\ & +\left(\frac{1}{2}+\sum _{u\in V_{P_1}}{s}_u+\frac{k+s_2-1}{2}\right)\left(\frac{1}{2}+\sum _{v\in V_{P_2}}{s}_v+\frac{k-s_2-1}{2}\right)\\ & -\frac{1}{2}\left(\sum _{w\in V_{P_1}\bigcup V_{P_2}}{s}_w+k-\frac{1}{2}\right)\\ & =\left(-\sum _{u\in V_{P_1}}{s}_u-\frac{k+s_2-1}{2}\right)x+\left(\sum _{u\in V_{P_1}}{s}_u+\frac{k+s_2-1}{2}\right)y\\ & +\left(\sum _{u\in V_{P_1}}{s}_u+\frac{k+s_2-1}{2}\right)\left(\sum _{v\in V_{P_2}}{s}_v+\frac{k-s_2-1}{2}\right)\\ & >\left(-\sum _{u\in V_{P_1}}{s}_u-\frac{k+s_2-1}{2}\right)x+\left(\sum _{u\in V_{P_1}}{s}_u+\frac{k+s_2-1}{2}\right)y\\ & +\frac{s_2+1}{2}\left(\sum _{v\in V_{P_2}}{s}_v-\frac{s_2+1}{2}\right).\end{array}

\begin{array}{rl}{L}_2& =\left(x+\sum _{u\in V_{P_1}}{s}_u+s_{u_{i+1}}-s_1+\frac{k-1}{2}+\frac{s_1+1}{2}\right)\\ & \left(y+\sum _{v\in V_{P_2}}{s}_v-s_{u_{i+1}}+\frac{k-1}{2}+\frac{s_1+1}{2}\right)\\ & -\left(x+\sum _{u\in V_{P_1}}{s}_u+s_{u_{i+1}}-s_1+\frac{k-1}{2}+\frac{s_1+s_2+2}{2}\right)\\ & \left(y+\sum _{v\in V_{P_2}}{s}_v-s_{u_{i+1}}-s_2+\frac{k-3}{2}+\frac{s_1+s_2+2}{2}\right)\\ & =\left(x+\sum _{u\in V_{P_1}}{s}_u+s_{u_{i+1}}+\frac{k-s_1}{2}\right)\left(y+\sum _{v\in V_{P_2}}{s}_v-s_{u_{i+1}}+\frac{k+s_1}{2}\right)\\ & -\left(x+\sum _{u\in V_{P_1}}{s}_u+s_{u_{i+1}}+\frac{k-s_1}{2}+\frac{s_2+1}{2}\right)\end{array}

\begin{array}{rl}& \left(y+\sum _{v\in V_{P_2}}{s}_v-s_{u_{i+1}}+\frac{k+s_1}{2}-\frac{s_2+1}{2}\right)\\ & =\frac{s_2+1}{2}\left(x+\sum _{u\in V_{P_1}}{s}_u+s_{u_{i+1}}+\frac{k-s_1}{2}\right)\\ & -\frac{s_2+1}{2}\left(y+\sum _{v\in V_{P_2}}{s}_v-s_{u_{i+1}}+\frac{k+s_1}{2}-\frac{s_2+1}{2}\right)\\ & =\frac{s_2+1}{2}x-\frac{s_2+1}{2}y+\frac{s_2+1}{2}\left(\sum _{u\in V_{P_1}}{s}_u-\sum _{v\in V_{P_2}}{s}_v+2s_{u_{i+1}}-s_1+\frac{s_2+1}{2}\right).\end{array}

\begin{array}{rl}{L}_3& =\left(x+\sum _{u\in V_{P_1}}{s}_u+\frac{k-1}{2}+\frac{s_{u_{i+1}}+1}{2}\right)\left(y+\sum _{v\in V_{P_2}}{s}_v-s_{u_{i+1}}+\frac{k-1}{2}+\frac{s_{u_{i+1}}+1}{2}\right)\\ & -\frac{1}{2}\left(x+y+\sum _{w\in V_{P_1}\bigcup V_{P_2}}{s}_w+k-\frac{1}{2}\right)\\ & =\left(\frac{1}{2}+x+\sum _{u\in V_{P_1}}{s}_u+\frac{k-2}{2}+\frac{s_{u_{i+1}}+1}{2}\right)\left(\frac{1}{2}+y+\sum _{v\in V_{P_2}}{s}_v+\frac{k}{2}-\frac{s_{u_{i+1}}+1}{2}\right)\\ & -\frac{1}{2}\left(x+y+\sum _{w\in V_{P_1}\bigcup V_{P_2}}{s}_w+k-\frac{1}{2}\right)\\ & =\left(x+\sum _{u\in V_{P_1}}{s}_u+\frac{k-2}{2}+\frac{s_{u_{i+1}}+1}{2}\right)\left(y+\sum _{v\in V_{P_2}}{s}_v+\frac{k}{2}-\frac{s_{u_{i+1}}+1}{2}\right)\\ & >\left(y+\sum _{v\in V_{P_2}}{s}_v+\frac{k}{2}-\frac{s_{u_{i+1}}+1}{2}\right)x+\left(\sum _{u\in V_{P_1}}{s}_u+\frac{k-2}{2}+\frac{s_{u_{i+1}}+1}{2}\right)y\\ & +\frac{s_{u_{i+1}}+1}{2}\left(\sum _{v\in V_{P_2}}{s}_v-\frac{s_{u_{i+1}}+1}{2}\right).\end{array}

\begin{array}{rl}{L}_4& =\left(\frac{x}{2}+\sum _{u\in V_{P_1}}{s}_u-\frac{s_{u_i}}{2}+s_2+\frac{k}{2}\right)\left(\frac{x}{2}+y+\sum _{v\in V_{P_2}}{s}_v+\frac{s_{u_i}}{2}-s_2+\frac{k}{2}\right)\\ & -\left(\frac{x}{2}+\sum _{u\in V_{P_1}}{s}_u-\frac{s_{u_i}}{2}+s_2+\frac{k}{2}+\frac{s_{u_{i+1}}+1}{2}\right)\end{array}

\begin{array}{rl}& \left(\frac{x}{2}+y+\sum _{v\in V_{P_2}}{s}_v+\frac{s_{u_i}}{2}-s_2+\frac{k}{2}-\frac{s_{u_{i+1}}+1}{2}\right)\\ & =\frac{s_{u_{i+1}}+1}{2}\left(\frac{x}{2}+\sum _{u\in V_{P_1}}{s}_u-\frac{s_{u_i}}{2}+s_2+\frac{k}{2}\right)\\ & -\frac{s_{u_{i+1}}+1}{2}\left(\frac{x}{2}+y+\sum _{v\in V_{P_2}}{s}_v+\frac{s_{u_i}}{2}-s_2+\frac{k}{2}-\frac{s_{u_{i+1}}+1}{2}\right)\\ & =-\frac{s_{u_{i+1}}+1}{2}y+\frac{s_{u_{i+1}}+1}{2}\left(\sum _{u\in V_{P_1}}{s}_u-\sum _{v\in V_{P_2}}{s}_v-s_{u_i}+2s_2+\frac{s_{u_{i+1}}+1}{2}\right).\end{array}

We know that {\text{Sz}}_e^{\ast }(G)-{\text{Sz}}_e^{\ast }(G^{{}^{\prime }})=L_1+L_2+L_3+L_4, so

\begin{array}{rl}& {\text{Sz}}_e^{\ast }\left(G\right)-{\text{Sz}}_e^{\ast }\left(G^{{}^{\prime }}\right)\\ & >\left(-\sum _{u\in V_{P_1}}{s}_u-\frac{k+s_2-1}{2}+\frac{s_2+1}{2}+y+\sum _{v\in V_{P_2}}{s}_v+\frac{k}{2}-\frac{s_{u_{i+1}}+1}{2}\right)x\\ & +\left(\sum _{u\in V_{P_1}}{s}_u+\frac{k+s_2-1}{2}-\frac{s_2+1}{2}+\sum _{u\in V_{P_1}}{s}_u+\frac{k-2}{2}+\frac{s_{u_{i+1}}+1}{2}-\frac{s_{u_{i+1}}+1}{2}\right)y\\ & +\left(\frac{s_2+1}{2}\right)\left(\sum _{v\in V_{P_2}}{s}_v-\frac{s_2+1}{2}+\sum _{u\in V_{P_1}}{s}_u-\sum _{v\in V_{P_2}}{s}_v+2s_{u_{i+1}}-s_1+\frac{s_2+1}{2}\right)\\ & +\left(\frac{s_{u_{i+1}}+1}{2}\right)\left(\sum _{v\in V_{P_2}}{s}_v-\frac{s_{u_{i+1}}+1}{2}+\sum _{u\in V_{P_1}}{s}_u-\sum _{v\in V_{P_2}}{s}_v-s_{u_i}+2s_2+\frac{s_{u_{i+1}}+1}{2}\right)\\ & =\left(y-\sum _{u\in V_{P_1}}{s}_u+\sum _{v\in V_{P_2}}{s}_v-\frac{s_{u_{i+1}}}{2}+\frac{1}{2}\right)x+\left(2\sum _{u\in V_{P_1}}{s}_u+k-2\right)y\\ & +\left(\frac{s_2+1}{2}\right)\left(\sum _{u\in V_{P_1}}{s}_u+2s_{u_{i+1}}-s_1\right)+\left(\frac{s_{u_{i+1}}+1}{2}\right)\left(\sum _{u\in V_{P_1}}{s}_u-s_{u_i}+2s_2\right)\\ & ⩾\left(y+\sum _{w\in V_{P_1}\bigcup V_{P_2}}{s}_w-\frac{s_{u_{i+1}}}{2}+k-\frac{3}{2}\right)x\left(\mathrm{b}\mathrm{e}\mathrm{c}\mathrm{a}\mathrm{u}\mathrm{s}\mathrm{e}x⩽y\right)\\ & >0.\end{array}

Continuing this process can ultimately transform into a case of 1 or 2.

Next, compare {\text{Sz}}_e^{\ast }(G_1), {\text{Sz}}_e^{\ast }(G_2), {\text{Sz}}_e^{\ast }(G_3), {\text{Sz}}_e^{\ast }(G_4) and {\text{Sz}}_e^{\ast }(G_5) (known m⩾20).

If d is odd, then

{\text{Sz}}_e^{\ast }(G_1)-{\text{Sz}}_e^{\ast }(G_5)=\frac{d^3-8d^2+15d-8}{4}-\frac{(d^2-8d+11)m}{4}>0(3⩽d⩽5).

If d is even, then

{\text{Sz}}_e^{\ast }(G_1)-{\text{Sz}}_e^{\ast }(G_2) ({\text{Sz}}_e^{\ast }(G_3)) ,

{\text{Sz}}_e^{\ast }(G_1)-{\text{Sz}}_e^{\ast }(G_5)=\frac{d^3-8d^2+16d-8}{4}-\frac{(d^2-8d+12)m}{4}>0(d=4).

G_4\cong G_5 for d=6. So, Theorem 1 is true.□

References

[1] Aouchiche M, Hansen P. On a conjecture about the Szeged index. European J Combin 2010; 31(7): 1662–1666

[2] BondyJ AMurtyU S R. Graph Theory. Graduate Texts in Mathematics, Vol 244, New York: Springer, 2008

[3] Chen L L, Li X L, Liu M M. On a relation between the Szeged and the Wiener indices of bipartite graphs. Trans Combin 2012; 1(4): 43–49

[4] Dobrynin A A. Graphs having the maximal value of the szeged index. Croat Chem Acta 1997; 70(3): 819–825

[5] Dobrynin A A, Entringer R, Gutman I. Wiener index of trees: theory and applications. Acta Appl Math 2001; 66(3): 211–249

[6] Dong H, Zhou B, Trinajsti N. A novel version of the edge-Szeged index. Croat Chem Acta 2011; 84(4): 543–545

[7] Graovac A, Pisanski T. On the Wiener index of a graph. J Math Chem 1991; 8(1/2/3): 53–62

[8] Gutman I. A formula for the Wiener number of trees and its extension to graphs containing cycles. Graph Theory Notes N Y 1994; 27: 9–15

[9] Gutman I, Ashrafi A R. The edge version of the Szeged index. Croat Chem Acta 2008; 81(2): 263–266

[10] Gutman I, Klavzar S, Mohar B. Fifty years of the Wiener index. MATCH Commun Math Comput Chem 1997; 35: 259

[11] Gutman I, Yeh Y N, Long S, Luo Y L. Some recent results in the theory of the Wiener number. Indian J Chem 1993; 32A: 651–661

[12] Ilic A. Note on PI and Szeged indices. Math Comput Model 2010; 52(9/10): 1570–1576

[13] Liu M M, Chen L L. Bicyclic graphs with maximal edge revised Szeged index. Discrete Appl Math 2016; 215: 225–230

[14] Liu M M, Wang S J. Cactus graphs with minimum edge revised Szeged index. Discrete Appl Math 2018; 247: 90–96

[15] Pisanski T, Zerovnik J. Edge-contributions of some topological indices and arboreality of molecular graphs. Ars Math Contemp 2009; 2(1): 49–58

[16] Randić . On generalization of Wiener index for cyclic structures. Acta Chim Slov 2002; 49: 483–496

[17] Simi S, Gutman I, Balti V. Some graphs with extremal Szeged index. Math Slovaca 2000; 50(1): 1–15

[18] Wang G F, Li S C, Qi D C, Zhang H H. On the edge-Szeged index of unicyclic graphs with given diameter. Appl Math Comput 2018; 336: 94–106

[19] Wiener H. Structural determination of paraffin boiling points. J Amer Chem Soc 1947; 69(1): 17–20

[20] Xing R D, Zhou B. On the revised Szeged index. Discrete Appl Math 2010; 159(1): 69–78

RIGHTS & PERMISSIONS

Higher Education Press 2023