For a connected graph \(G\), the edge Mostar index \(Mo_e(G)\) is defined as \(Mo_e(G)=\sum\limits_{e=uv \in E(G)}|m_u(e|G) – m_v(e|G)|\), where \(m_u(e|G)\) and \(m_v(e|G)\) are respectively, the number of edges of \(G\) lying closer to vertex \(u\) than to vertex \(v\) and the number of edges of \(G\) lying closer to vertex \(v\) than to vertex \(u\). We determine a sharp upper bound for the edge Mostar index on bicyclic graphs and identify the graphs that achieve the bound, which disproves a conjecture proposed by Liu et al. [Iranian J. Math. Chem. 11(2) (2020) 95–106].
Let \(G\) be a graph with vertex set \(V(G)\) and edge set \(E(G)\). The order and size of \(G\) are the cardinality of \(V(G)\) and \(E(G)\), respectively. The distance between \(u\) and \(v\) in \(G\), denoted by \(d_G(u,v)\), is the shortest path connecting \(u\) and \(v\) in \(G\). For a vertex \(x\) and edge \(e = uv\) of a graph \(G\), the distance between \(x\) and \(e\), denoted by \(d_G (x, e)\) , is defined as \(d_G (x, e)= min\{ d_G(x,u), d_G(x,v)\}\).
A molecular graph is a simple graph such that its vertices correspond to the atoms and the edges to the bonds of a molecule. A topological graph index, also called a molecular descriptor, is a mathematical formula that can be applied to any graph which models some molecular structure. From this index, it is possible to analyse mathematical values and further investigate some physicochemical properties of a molecule. Therefore, it is an efficient method in avoiding expensive and time-consuming laboratory experiments.
Došlić et al. [7] introduced the Mostar index, which is a measure of peripherality in graphs. It can also be considered as a bond-additive structural invariant as a quantitative refinement of the distance non-balancedness. For a graph \(G\), the Mostar index is defined as \[Mo(G)=\sum_{e=uv \in E(G)}|n_u(e|G) – n_v(e|G)|.\] where \(n_u(e|G)\) is the number of vertices of \(G\) closer to \(u\) than to \(v\) and \(n_v(e|G)\) is the number of vertices closer to \(v\) than to \(u\).
Since its introduction in 2018, the Mostar index has already incited a lot of research, mostly concerning trees [1,6,5,4,8,12,14], unicyclic graphs [18], bicyclic graphs [20], tricyclic graphs [11], cacti [13] and chemical graphs [3,16,21,22].
Arockiaraj et al. [2], introduced the edge Mostar index as a quantitative refinement of the distance non-balancedness, also measure the peripherality of every edge and consider the contributions of all edges into a global measure of peripherality for a given chemical graph. The edge Mostar index of \(G\) is defined as \[Mo_e(G)=\sum_{e=uv \in E(G)}\psi_G(uv),\] where \(\psi_G(uv)=|m_u(e|G) – m_v(e|G)|\), \(m_u(e|G)\) and \(m_v(e|G)\) are respectively, the number of edges of \(G\) lying closer to vertex \(u\) than to vertex \(v\) and the number of edges of \(G\) lying closer to vertex \(v\) than to vertex \(u\). We use \(\psi(uv)=|m_u(e) – m_v(e)|\) for short, if there is no ambiguity.
The problem of determining which graphs uniquely maximize (resp. minimize) the edge Mostar index in various classes of graphs has received much attention. For example, Imran et al. [17] studied the edge Mostar index of chemical structures and nanostructures using graph operations. Havare [10] computed the edge Mostar index for several classes of cycle-containing graphs. Hayat et al. [15] obtained a sharp upper bound for the edge Mostar index on tricyclic graphs and identified the graphs that attain the bound. Liu et al. [19] determined the extremal values of the edge Mostar index among trees, unicyclic graphs, cacti and posed two conjectures for the extremal edge Mostar index among bicyclic graphs. Ghalavand et al. [9] gave proof to a conjecture in [19], and obtained the graph that minimizes the edge Mostar index among bicyclic graphs.
Motivated directly by [19] and [9], we determine the unique graph that maximizes the edge Mostar index over all bicyclic graphs with fixed size, which disproves the following conjecture.
[19] If the size \(m\) of bicyclic graphs is large enough, then the bicyclic graphs \(B_m\) (see Figure 1) and \(B^5_m\) (see Figure 2) have the maximum edge Mostar index.
We disprove Conjecture 1.1, by presenting the following result.
Let \(G\) be a bicyclic graph of size \(m \geq 5\). Then \[Mo_e(G) \leq \left\{\begin{array}{ll} 4, & \hbox{if $m=5$, and equality holds iff $G \cong B^3_m, B^4_m$}; \\ m^2-3m-6, & \hbox{if $6 \leq m \leq 8$, and equality holds iff $G \cong B^1_m, B^3_m$}; \\ 48, & \hbox{if $m=9$, and equality holds iff $G \cong B_m, B^1_m, B^2_m, B^3_m, B^4_m$}; \\ m^2-m-24, & \hbox{if $m \geq 10$, and equality holds iff $G \cong B_m$}. \end{array}\right.\] (Where \(B_m, B^1_m, B^2_m\) and \(B^3_m, B^4_m\) are depicted in Figure 1 and Figure 2, respectively).
Based on the above Theorem, if the size \(m\) of bicyclic graphs is large, then \(B_m\) is the unique graph that maximizes the edge Mostar index. Therefore, Conjecture 1.1 is disproved.
In Section 2, we provide some definitions and preliminary results. The proof of Theorem 1.2 is presented in Section 3.
In this section, we present some basic notations and elementary results, which will be useful in the proof of our main result.
For \(v \in V(G)\), let \(N_G(v)\) be the set of vertices that are adjacent to \(v\) in \(G\). The degree of \(v \in V(G)\), denoted by \(d_G(v)\), is the cardinality of \(N_G(v)\). A vertex with degree one is called a pendent vertex and an edge incident to a pendent vertex is called a pendent edge. A graph \(G\) with \(n\) vertices is a bicyclic graph if \(|E(G)|=n+1\). As usual by \(S_n\), \(P_n\), and \(C_n\) we denote the star, path, and cycle graph on \(n\) vertices, respectively.
The join of two graphs \(G_1\) and \(G_2\) is denoted by \(G_1 \cdot G_2\), is obtained by identifying one vertex from \(G_1\) and \(G_2\). Let \(u\) be the identified vertex in both \(G_1\) and \(G_2\). If \(G_1\) contains a cycle and \(u\) belongs to some cycle, while \(G_2\) is a tree, then we call \(G_2\) a pendent tree in \(G_1 \cdot G_2\) associated with \(u\).
For each \(e \in E(G_1)\), every path from \(e\) to some edges in \(G_2\) pass through \(u\). Therefore, the contribution of \(G_2\) to \(\sum_{e\in E(G_1)}\psi(e)\) totally depends on the size of \(G_2\). In other words, changing the structure of \(G_2\) does not affect the value of \(\sum_{e\in E(G_1)}\psi(e)\).
[19] Let \(G\) be a graph of size \(m\) with a cut edge \(e=uv\). Then \(\psi(e)\leq m-1\) with equality if and only if \(e=uv\) is a pendent edge.
By Lemma 2.1, if \(e\) is a pendent edge, then \(\psi(e)\) is maximum. Therefore, it is easy to verify the following result.
Let \(H\) be a graph of size \(m\). Then \[Mo_e(H_1 \cdot H)\leq Mo_e(H_1 \cdot S_m),\] where the common vertex of \(H_1\) and \(S_m\) is the center of \(S_m\), while the common vertex of \(H_1\) and \(H\) can be chosen arbitrarily.
Let \(S_{m,r} = S_{m-r} \cdot C_r\), where the common vertex of \(S_{m-r}\) and \(C_r\) is the center of \(S_{m-r}\).
[19] Let \(G\) be a unicyclic graph of size \(m \geq 3\). Then \[Mo_e(G) \leq \left\{\begin{array}{ll} m^2-2m-3, & \hbox{if $3 \leq m \leq 8$, and equality holds iff $G \cong S_{m, 3} $}; \\ 60, & \hbox{if $m=9$, and equality holds iff $G \cong S_{m, 3}, S_{m, 4} $}; \\ m^2-m-12, & \hbox{if $m \geq 10$, and equality holds iff $G \cong S_{m, 4} $}. \end{array}\right.\]
Let \(G_1\) be a connected graph of size \(m_1\) and \(G_2\) be a unicyclic graph of size \(m_2\). Then \[Mo_e(G_1 \cdot G_2 ) \leq \left\{\begin{array}{ll} Mo_e(G_1 \cdot S_{m_2, 3} ) & \hbox{for $m_1 + m_2 \leq 8$}; \\ Mo_e(G_1 \cdot S_{m_2, 3} )= Mo_e(G_1 \cdot S_{m_2, 4} ) & \hbox{for $m_1 + m_2 = 9$}; \\ Mo_e(G_1 \cdot S_{m_2, 4} ) & \hbox{for $m_1 + m_2 \geq 10$}; \end{array}\right.\] where the common vertex of \(G_1\) and \(S_{m_2, 3}\) (resp. \(G_1\) and \(S_{m_2, 4}\)) is the center of \(S_{m_2, 3}\) (resp. \(S_{m_2, 4}\)), while the common vertex of \(G_1\) and \(G_2\) can be chosen arbitrarily.
Proof. If \(m_1 + m_2 \leq 8\), then by Lemma 2.3, we have \[\begin{aligned} Mo_e(G_1 \cdot G_2 ) & = \sum_{e=uv \in E(G_1 \cdot G_2)}\psi_{G_1 \cdot G_2}(uv) \\ & = \sum_{e=uv \in E(G_1)}\psi_{G_1 \cdot G_2}(uv) + \sum_{e=uv \in E( G_2)}\psi_{G_1 \cdot G_2}(uv) \\ & = \sum_{e=uv \in E(G_1)}\psi_{G_1 \cdot G_2}(uv) + Mo_e(S_{m_1} \cdot G_2 )-m_1(m-1) \\ &\leq \sum_{e=uv \in E(G_1)}\psi_{G_1 \cdot S_{m_2, 3}}(uv) + Mo_e(S_{m_1} \cdot S_{m_2, 3})-m_1(m-1) \\ & = \sum_{e=uv \in E(G_1)}\psi_{G_1 \cdot S_{m_2, 3}}(uv) + \sum_{e=uv \in E( S_{m_2, 3})}\psi_{G_1 \cdot S_{m_2, 3}}(uv) \\ & = Mo_e(G_1 \cdot S_{m_2, 3} ). \end{aligned}\]
Similarly, if \(m_1 + m_2 = 9\), then \(Mo_e(G_1 \cdot G_2 ) \leq Mo_e(G_1 \cdot S_{m_2, 3} )= Mo_e(G_1 \cdot S_{m_2, 4} )\); if \(m_1 + m_2 \geq 10\), then \(Mo_e(G_1 \cdot G_2 ) \leq Mo_e(G_1 \cdot S_{m_2, 4} )\). ◻
The \(\Theta\)-graph is a graph that connects two fixed vertices with three internally disjoint paths. If the lengths of these paths are \(l_1, l_2\), and \(l_3\) where \(l_1 \leq l_2 \leq l_3\), the graph is denoted as \(\Theta (l_1, l_2, l_3)\).
Let \(\mathcal{G}_m^1\) represent the set of bicyclic graphs of size \(m\) that contain exactly two edge-disjoint cycles. Let \(\mathcal{G}_m^2\) denote the set of bicyclic graphs of size \(m\) that contain exactly three cycles. Moreover, if \(G \in \mathcal{G}_m^2\), then \(G\) contains a \(\Theta\)-graph as a subgraph, which is called as the brace of \(G\).
For the proof of Theorem 1.2, we first develop several lemmas. In the first step, we establish a sharp upper bound for \(Mo_e(G)\) on the set \(\mathcal{G}_m^1\).
Let \(G \in \mathcal{G}_m^1\) . Then \[Mo_e(G) \leq \left\{\begin{array}{ll} m^2-3m-6, & \hbox{if $6 \leq m \leq 8$, and equality holds iff $G \cong B^2_m$}; \\ 48, & \hbox{if $ m=9$, and equality holds iff $G \cong B_m, B^1_m, B^2_m$}; \\ m^2-m-24, & \hbox{if $m \geq 10$, and equality holds iff $G \cong B_m$}. \end{array}\right.\]
Proof. Let \(G \in \mathcal{G}_m^1\). Then there are two unicyclic graphs \(G_1\) and \(G_2\) with size \(m_1\) and \(m_2\), respectively such that \(G = G_1 \cdot G_2\). Then, in view of Lemma 2.4. If \(6 \leq m \leq 8\), we get \[\begin{aligned} Mo_e(G ) & = Mo_e(G_1 \cdot G_2 ) \leq Mo_e(G_1 \cdot S_{m_2, 3} )\\ &\leq Mo_e(S_{m_1, 3} \cdot S_{m_2, 3} )= Mo_e(B^2_m); \end{aligned}\] if \(m= 9\), then \[\begin{aligned} Mo_e(G ) & = Mo_e(G_1 \cdot G_2 ) \leq Mo_e(G_1 \cdot S_{m_2, 3} )= Mo_e(G_1 \cdot S_{m_2, 4} )\\ &\leq Mo_e(S_{m_1, 3} \cdot S_{m_2, 3} )= Mo_e(S_{m_1, 3} \cdot S_{m_2, 4} )= Mo_e(B^2_m)\\ & = Mo_e(S_{m_1, 4} \cdot S_{m_2, 4} ) = Mo_e(B_m) = Mo_e(B^1_m)= Mo_e(B^2_m). \end{aligned}\]
If \(m \geq 10\), we have \[\begin{aligned} Mo_e(G ) & = Mo_e(G_1 \cdot G_2 ) \leq Mo_e(G_1 \cdot S_{m_2, 4} )\\ &\leq Mo_e(S_{m_1, 4} \cdot S_{m_2, 4} )= Mo_e(B_m). \end{aligned}\]
By simple calculation, we get \(Mo_e(B_m)= m^2-m-24\), \(Mo_e(B^1_m)= m^2-2m-15\), and \(Mo_e(B^2_m)= m^2-3m-6\). If \(m=9\), then \(Mo_e(B_m)= Mo_e(B^1_m)=Mo_e(B^2_m)= 48\). This completes the proof. ◻
In the following, we determine a sharp upper bound for \(Mo_e(G)\) on the set \(\mathcal{G}_m^2\).
Let \(G \in \mathcal{G}_m^2\) with brace \(\Theta (1,2,2)\). Then \[Mo_e(G) \leq \left\{\begin{array}{ll} 4, & \hbox{if $m=5$, and equality holds iff $G \cong B^3_m, B^4_m$}; \\ m^2-3m-6, & \hbox{if $6 \leq m \leq 8$, and equality holds iff $G \cong B^3_m$}; \\ 48, & \hbox{if $ m=9$, and equality holds iff $G \cong B^3_m, B^4_m$}; \\ m^2-2m-15, & \hbox{if $m \geq 10$, and equality holds iff $G \cong B^4_m$}. \end{array}\right.\]
Proof. Let \(G \in \mathcal{G}_m^2\) with brace \(\Theta (1,2,2)\). Suppose that \(v_1, v_2, v_3, v_4\) be the vertices in \(\Theta (1,2,2)\) of \(G\) with \(d_G(v_1)=d_G(v_2)=3\), and \(d_G(v_3)=d_G(v_4)=2\). Let \(a_i\) be the number of pendent edges of \(v_i\) (\(i=1,2,3,4\)). Suppose that \(a_1 \geq a_2\) and \(a_3 \geq a_4\). Let \(G_1\) be the graph obtained from \(G\) by shifting \(a_2\) pendent edges from \(v_2\) to \(v_1\). We have \[\begin{aligned} Mo_e(G_1 )- Mo_e(G ) =& (a_1+a_2+2-2)-(a_1+2-a_2-2) + (a_1+a_2+a_4+2-a_3-1)\\ &-(a_1+a_4+2-a_3-1)+(a_1+a_2+a_3+2-a_4-1) \\&- (a_1+a_3+2-a_4-1)+(a_4+2-a_3-1)-(a_2+a_4+2-a_3-1)\\ &+(a_3+2-a_4-1)-(a_2+a_3+2-a_4-1)= 2a_2 \geq 0. \end{aligned}\]
Hence, \(Mo_e(G_1 ) \geq Mo_e(G )\) and equality holds if and only if \(a_2 =0\), i.e., \(G \cong G_1\).
Let \(G_2\) be the graph obtained from \(G_1\) by shifting \(a_4\) pendent edges from \(v_4\) to \(v_3\). We have \[\begin{aligned} Mo_e(G_2 )- Mo_e(G_1) =&(a_1+2-2)-(a_1+2-2)+(a_3+a_4+1-a_1-2)\\ &-(a_3+1-a_1-a_4-2)+(a_1+a_3+a_4+2-1)\\&-(a_1+a_3+2-a_4-1)+ (a_3+a_4+1-2)\\&-(a_3+1-a_4-2)+(a_3+a_4+2-1)-(a_3+2-a_4-1)\\ =& 8a_4 \geq 0. \end{aligned}\]
Hence, \(Mo_e(G_2 ) \geq Mo_e(G_1 )\) and equality holds if and only if \(a_4 =0\), i.e., \(G_2 \cong G_1\).
Let \(G_3\) be the graph obtained from \(G_2\) by shifting \(a_1\) pendent edges from \(v_1\) to \(v_3\). We have \[\begin{aligned} Mo_e(G_3 )- Mo_e(G_2) =& -(a_1+2-2)+(a_1+a_3+1-2)-(a_3+1-a_1-2)\\ &+ (a_1+a_3+2-1)-(a_1+a_3+2-1)+(a_1+a_3+1-2)\\&-(a_3+1-2) + (a_1+a_3+2-1)-(a_3+2-1)\\ = & 3a_1 \geq 0. \end{aligned}\]
Hence, \(Mo_e(G_3 ) \geq Mo_e(G_2 )\) and equality holds if and only if \(a_1 =0\), i.e., \(G_3 \cong G_2\). Clearly, \(G_2 \cong B^3_m\) with \(a_3= 0\), and \(G_3 \cong B^4_m\). Also, by simple calculation, we have \(Mo_e(B^3_m)= m^2-3m-6\), \(Mo_e(B^4_m)= m^2-2m-15\). ◻
Let \(G \in \mathcal{G}_m^2\) with brace \(\Theta (2,2,2)\). If \(m \geq 6\), then \(Mo_e(G) \leq m^2-m-28\) with equality if and only if \(G \cong B^5_m\) (see Figure 2).
Proof. Let \(G \in \mathcal{G}_m^2\) with brace \(\Theta (2,2,2)\). Let \(v_1, v_2, v_3, v_4, v_5\) be vertices in \(\Theta (2,2,2)\) of \(G\) with \(d_G(v_1)=d_G(v_2)=3\) and \(d_G(v_3)=d_G(v_4)=d_G(v_5)=2\). Let \(a_i\) be the number of pendent edges of \(v_i\) (\(i=1,2,3,4,5\)). Suppose that \(a_1 \geq a_2\) and \(a_3 \geq a_4 \geq a_5\). Let \(G_1\) be the graph obtained from \(G\) by shifting \(a_2\) pendent edges from \(v_2\) to \(v_1\). We have \[\begin{aligned} Mo_e(G_1 )- Mo_e(G )=& (a_1+a_2+a_4+a_5+2-a_3-1)- (a_1+a_4+a_5+2-a_2-a_3-1)\\&+(a_1+a_2+a_3+a_5+2-a_4-1)- (a_1+a_3+a_5+2-a_2-a_4-1)\\&+(a_1+a_2+a_3+a_4+2-a_5-1)- (a_1+a_3+a_4+2-a_2-a_5-1)\\&+(a_1+a_2+a_3+1-a_4-a_5-2)- (a_1+a_3+1-a_2-a_4-a_5-2)\\&+(a_1+a_2+a_4+1-a_3-a_5-2)-(a_1+a_4+1-a_2-a_3-a_5-2)\\&+(a_1+a_2+a_5+1-a_3-a_4-2)-(a_1+a_5+1-a_2-a_3-a_4-2)\\ = & 12a_2 \geq 0. \end{aligned}\]
Hence, \(Mo_e(G_1 ) \geq Mo_e(G )\) and equality holds if and only if \(a_2 =0\), i.e., \(G \cong G_1\).
Let \(G_2\) be the graph obtained from \(G_1\) by shifting \(a_5\) pendent edges from \(v_5\) to \(v_3\). We get \[\begin{aligned} Mo_e(G_2 )- Mo_e(G_1 ) = & (a_3+a_5+1-a_1-a_4-2)-(a_3+1-a_1-a_4-a_5-2)\\ & + (a_1+a_3+a_5+2-a_4-1)-(a_1+a_3+a_5+2-a_4-1)\\ &+ (a_1+a_3+a_4+a_5+2-1)-(a_1+a_3+a_4+2-a_5-1)\\ &+ (a_1+a_3+a_5+1-a_4-2)-(a_1+a_3+1-a_4-a_5-2)\\ &+ (a_3+a_5+2-a_1-a_4-1)-(a_3+a_5+2-a_1-a_4-1)\\ &+ (a_3+a_4+a_5+2-a_1-1)-(a_3+a_4+2-a_1-a_5-1)\\ = & 8 a_5 \geq 0. \end{aligned}\]
Hence, \(Mo_e(G_2 ) \geq Mo_e(G_1 )\) and equality holds if and only if \(a_5 =0\), i.e., \(G_2 \cong G_1\).
Let \(G_3\) be the graph obtained from \(G_2\) by shifting \(a_4\) pendent edges from \(v_4\) to \(v_3\). By symmetry, \(Mo_e(G_3 ) \geq Mo_e(G_2 )\), and equality holds if and only if \(G_3 \cong G_2\). Let \(G_4\) be the graph obtained from \(G_3\) by shifting \(a_1\) pendent edges from \(v_1\) to \(v_3\). We get \[\begin{aligned} Mo_e(G_4 )- Mo_e(G_3)= & (a_1+a_3+1-2)-(a_3+1-a_1-2)+(a_1+a_3+2-1)\\&-(a_1+a_3+2-1)+ (a_1+a_3+2-1)-(a_1+a_3+2-1)\\ &+(a_1+a_3+1-2)-(a_1+a_3+1-2)+(a_1+a_3+2-1)\\&-(a_3+2-a_1-1) + (a_1+a_3+2-1)-(a_3+2-a_1-1) \\=& 6a_1 \geq 0. \end{aligned}\]
Hence, \(Mo_e(G_4 ) \geq Mo_e(G_3 )\) and equality holds if and only if \(a_1 =0\), i.e., \(G_4 \cong G_3\). Note that \(G_4 \cong B^5_m\). Clearly, \(Mo_e(B^5_m )=m^2-m-28\). ◻
Let \(G \in \mathcal{G}_m^2\) with brace \(\Theta (1,2,3)\). If \(m \geq 6\), then \(Mo_e(G) \leq m^2-2m-16\) with equality if and only if \(G \cong B^6_m\) (see Figure 2).
Proof. Let \(G \in \mathcal{G}_m^2\) with brace \(\Theta (1,2,3)\). Let \(v_1, v_2, v_3, v_4, v_5\) be vertices in \(\Theta (1,2,3)\) of \(G\) with \(d_G(v_1)=d_G(v_2)=3\) and \(d_G(v_3)=d_G(v_4)=d_G(v_5)=2\). Let \(a_i\) be the number of pendent edges of \(v_i\) (\(i=1,2,3,4,5\)). Suppose that \(a_1 + a_4 \geq a_2 + a_5\) . Let \(G_1\) be the graph obtained from \(G\) by shifting \(a_2\) (resp. \(a_5\)) pendent edges from \(v_2\) (resp. \(v_5\)) to \(v_1\) (resp. \(v_4\)). We deduce that \[\begin{aligned} Mo_e(G_1 )- Mo_e(G ) =& (a_1+a_2+a_4+a_5+2-2)-(a_1+a_4+2-a_2-a_5-2)\\ &+ (a_1+a_2+a_4+a_5+3-a_3-1)-(a_1+a_4+3-a_3-1)\\&+(3-a_3-1) – (a_2+a_5+3-a_3-1)\\&+(a_1+a_2+a_3+3-a_4-a_5-1) – (a_1+a_2+a_3+3-a_4-a_5-1)\\&+(a_1+a_2+a_3+3-a_4-a_5-1) – (a_1+a_2+a_3+3-a_4-a_5-1)\\&+(a_1+a_2+a_4+a_5+2-2) – (a_1+a_4+2-a_2-a_5-2)\\ = & 4( a_2 + a_5 ) \geq 0. \end{aligned}\]
Hence, \(Mo_e(G_1 ) \geq Mo_e(G )\) and equality holds if and only if \(a_2= a_5 =0\), i.e., \(G \cong G_1\).
Let \(G_2\) be the graph obtained from \(G_1\) by shifting \(a_4\) pendent edges from \(v_4\) to \(v_1\). We obtain \[\begin{aligned} Mo_e(G_2 )- Mo_e(G_1)= & (a_1+a_4+2-2)-(a_1+a_4+2-2)\\ &+ (a_1+a_4+3-a_3-1)-(a_1+a_4+3-a_3-1)+(3-a_3-1)\\ &- (3-a_3-1)+(a_1+a_3+a_4+3-1)-(a_1+a_3+3-a_4-1)\\ &+ (a_1+a_3+a_4+3-1)-(a_1+a_3+3-a_4-1)\\ &+ (a_1+a_4+2-2)-(a_1+a_4+2-2)\\ = & 4 a_4 + a_1 -a_3 \geq 0. \end{aligned}\]
Hence, \(Mo_e(G_2 ) \geq Mo_e(G_1 )\) and equality holds if and only if \(a_4 =0, a_1= a_3\), i.e., \(G_2 \cong G_1\).
Let \(G_3\) be the graph obtained from \(G_2\) by shifting \(a_3\) pendent edges from \(v_3\) to \(v_1\). We have \[\begin{aligned} Mo_e(G_3 )- Mo_e(G_2)=& (a_1+a_3+2-2)-(a_1+2-2)+(a_1+a_3+3-1)\\ &-(a_1+3-a_3-1)+(a_1+a_3+3-1)-(a_1+a_3+3-1)\\&+(a_1+a_3+2-2) -(a_1+2-2)+(3-1)-(3-a_3-1)\\&+(a_1+a_3+3-1)-(a_1+a_3+3-1) = 5a_3 \geq 0. \end{aligned}\]
Hence, \(Mo_e(G_3 ) \geq Mo_e(G_2 )\) and equality holds if and only if \(a_3 =0\), i.e., \(G_3 \cong G_2\). Note that \(G_3 \cong B^6_m\). Clearly, \(Mo_e(B^6_m )=m^2-2m-16\). ◻
Let \(G \in \mathcal{G}_m^2\) with brace \(\Theta (a,b,c)\). Then \[Mo_e(G) \leq \left\{\begin{array}{ll} 4, & \hbox{if $m=5$, and equality holds iff $G \cong B^3_m, B^4_m$}; \\ m^2-3m-6, & \hbox{if $6 \leq m \leq 8$, and equality holds iff $G \cong B^3_m$}; \\ 48, & \hbox{if $ m=9$, and equality holds iff $G \cong B^3_m, B^4_m$}; \\ m^2-2m-15, & \hbox{if $10 \leq m \leq 12$, and equality holds iff $G \cong B^4_m$}; \\ 128, & \hbox{if $ m=13$, and equality holds iff $G \cong B^4_m, B^5_m$}; \\ m^2-m-28, & \hbox{if $ m \geq 14$, and equality holds iff $G \cong B^5_m$.} \end{array}\right.\]
Proof. Suppose that \(x\) and \(y\) are the vertices with degree 3 in \(\Theta (a,b,c)\) of \(G\). Let \(P_{a+1}, P_{b+1}, P_{c+1}\) be the three disjoint paths connecting \(x\) and \(y\). We now proceed by considering the following three possible cases.
Case 1. \(c \geq b \geq a \geq 3\).
Subcase 1.1. \(c = b = a \geq 3\).
We choose six edges such that each one is incident to \(x\) or \(y\) in \(\Theta (a,b,c)\). Let \(e\) be one of these six edges. Then \(\psi(e) \leq m-7\). This property holds for the remaining five edges as well. Therefore, \[Mo_e(G) \leq 6(m-7)+(m-6)(m-1) < m^2-m-28.\]
Subcase 1.2. \(c \geq b \geq 4, a = 3\).
Let \(e_1\) be one of the four edges incident to \(x\) or \(y\) in the paths \(P_{b+1}\) and \(P_{c+1}\), and \(e_2\) be one of the two edges incident to \(x\) or \(y\) in the path \(P_{a+1}\). Then \(\psi(e_1) \leq m-8\), and \(\psi(e_2) \leq m-9\). Hence, \[Mo_e(G) \leq 4(m-8)+2(m-9)+(m-6)(m-1) < m^2-m-28.\]
Case 2. \(c \geq b \geq a =2\).
Subcase 2.1. \(c = b = a =2\).
The Subcase follows from Lemma 3.3.
Subcase 2.2. \(c \geq 3, b = a =2\).
Let \(e_1\) be one of the four edges in the paths \(P_{a+1}\) and \(P_{b+1}\), and \(e_2\) be one of the two edges incident to \(x\) or \(y\) in the path \(P_{c+1}\). Then \(\psi(e_1) \leq m-7\), and \(\psi(e_2) \leq m-6\). Hence, \[Mo_e(G) \leq 4(m-7)+2(m-6)+(m-6)(m-1) < m^2-m-28.\]
Subcase 2.3. \(c \geq b \geq 3, a =2\).
Let \(e_1\) be one of the four edges incident to \(x\) or \(y\) in the paths \(P_{b+1}\) and \(P_{c+1}\), and \(e_2\) is an edge in the path \(P_{a+1}\). Then \(\psi(e_1) \leq m-6\), and \(\psi(e_2) \leq m-9\). Hence, \[Mo_e(G) \leq 4(m-6)+2(m-9)+(m-6)(m-1) < m^2-m-28.\]
Case 3. \(c \geq b \geq 2 \geq a =1\).
Subcase 3.1. \(c = b =3, a =1\).
By Lemma 3.2 and simple calculation, we have if \(m \geq 14\), then \(Mo_e(B^5_m) > Mo_e(B^4_m)\); if \(m=13\), then \(Mo_e(B^3_m) = Mo_e(B^4_m) > Mo_e(B^5_m)\); if \(10 \leq m \leq 12\), then \(Mo_e(B^4_m) > Mo_e(B^5_m)\); if \(m=9\), then \(Mo_e(B^3_m) = Mo_e(B^4_m) > Mo_e(B^5_m)\); if \(6 \leq m \leq 8\), \(Mo_e(B^3_m) > Mo_e(B^4_m) > Mo_e(B^5_m)\); if \(m=5\), then \(Mo_e(B^3_m) = Mo_e(B^4_m)\).
Subcase 3.2. \(c = 3, b =2, a =1\).
This Subcase follows from Lemma 3.4.
Subcase 3.3. \(c \geq 4, b =2, a =1\).
Let \(e_1=xy\), \(e_2\) be one of the four edges in the paths \(P_{b+1}\) and \(P_{c+1}\) that are incident to \(x\) or \(y\), and \(e_3\) be one of the two edges in the middle of the path \(P_{c+1}\). Then \(\psi(e_1) = 0\), \(\psi(e_2) \leq m-5\), and \(\psi(e_3) \leq m-6\). Thus, \[Mo_e(G) \leq 4(m-5)+2(m-6)+(m-7)(m-1) < m^2-m-28.\]
Subcase 3.4. \(c \geq 4, b =3, a =1\).
Let \(e_1=xy\), \(e_2\) be one of the two edges in the path \(P_{b+1}\) that are incident to \(x\) or \(y\), \(e_3\) be one of the two edges in the path \(P_{c+1}\) that are incident to \(x\) or \(y\), and \(e_4\) be one of the two edges in the middle of the path \(P_{c+1}\). Then \(\psi(e_1) = 0\), \(\psi(e_2) \leq m-4\), \(\psi(e_2) \leq m-5\), and \(\psi(e_4) \leq m-6\). Hence, \[Mo_e(G) \leq 2(m-4)+2(m-5)+2(m-6)+(m-7)(m-1) < m^2-m-28. \] ◻
The proof of Theorem 1.2 directly follows from Lemmas 3.1 and 3.5.
The authors express their gratitude to the anonymous referee for their insightful comments and helpful suggestions. This work was supported by the National Natural Science Foundation of China (Grant Nos. 12071194, 11571155 and 12071158).
The authors declare no conflict of interest.
1970-2025 CP (Manitoba, Canada) unless otherwise stated.