Disproof of a conjecture on the edge mostar index

Hayat, Fazal; Xu, Shou-Jun; Zhou, Bo

doi:10.61091/um121-03

Abstract

1. Introduction
2. Preliminaries
3. Proof of theorem 1.2
Acknowledgements
Declarations

References

Utilitas Mathematica

Volume 121
Pages: 25-35

Research article

Disproof of a conjecture on the edge mostar index

^¹, ^¹, ^²

¹School of Mathematics and Statistics, Gansu Center for Applied Mathematics, Lanzhou University, Lanzhou 730000, China

²School of Mathematical Sciences, South China Normal University, Guangzhou 510631, China

Received: 31/08/2024
Accepted: 28/11/2024
Published: 31/12/2024

Copyright Link
License

Abstract

For a connected graph $G$ , the edge Mostar index $M o_{e} (G)$ is defined as $M o_{e} (G) = \sum_{e = u v \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].

Keywords: Mostar index, Edge Mostar index, Bicyclic graph, Distance-balanced graph

1. Introduction

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 = u v$ of a graph $G$ , the distance between $x$ and $e$ , denoted by $d_{G} (x, e)$ , is defined as $d_{G} (x, e) = m i n {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 $M o (G) = \sum_{e = u v \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 $M o_{e} (G) = \sum_{e = u v \in E (G)} ψ_{G} (u v),$ where $ψ_{G} (u v) = | 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 $ψ (u v) = | 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.

Conjecture 1.1.

[19] If the size $m$ of bicyclic graphs is large enough, then the bicyclic graphs $B_{m}$ (see Figure 1) and $B_{m}^{5}$ (see Figure 2) have the maximum edge Mostar index.

We disprove Conjecture 1.1, by presenting the following result.

Theorem 1.2.

Let $G$ be a bicyclic graph of size $m \geq 5$ . Then $M o_{e} (G) \leq {\begin{cases} 4, & if m = 5, and equality holds iff G ≅ B_{m}^{3}, B_{m}^{4}; \\ m^{2} - 3 m - 6, & if 6 \leq m \leq 8, and equality holdsiff G ≅ B_{m}^{1}, B_{m}^{3}; \\ 48, & if m = 9, and equality holds iff G ≅ B_{m}, B_{m}^{1}, B_{m}^{2}, B_{m}^{3}, B_{m}^{4}; \\ m^{2} - m - 24, & if m \geq 10, and equality holds iff G ≅ B_{m} . \end{cases}$ (Where $B_{m}, B_{m}^{1}, B_{m}^{2}$ and $B_{m}^{3}, B_{m}^{4}$ 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.

2. Preliminaries

In this section, we present some basic notations and elementary results, which will be useful in the proof of our main result.

Figure 1 The graphs $B_{m}, B_{m}^{1}$ , and $B_{m}^{2}$ , each of size $m$ , have $m - 8$ , $m - 7$ , and $m - 6$ pendent edges, respectively

Figure 2 The graphs $B_{m}^{3}, B_{m}^{4}, B_{m}^{5}$ , and $B_{m}^{6}$ of size $m$ , have $m - 5$ , $m - 5$ , $m - 6$ , and $m - 6$ pendent edges, respectively

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})} ψ (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})} ψ (e)$ .

Lemma 2.1.

[19] Let $G$ be a graph of size $m$ with a cut edge $e = u v$ . Then $ψ (e) \leq m - 1$ with equality if and only if $e = u v$ is a pendent edge.

By Lemma 2.1, if $e$ is a pendent edge, then $ψ (e)$ is maximum. Therefore, it is easy to verify the following result.

Lemma 2.2.

Let $H$ be a graph of size $m$ . Then $M o_{e} (H_{1} \cdot H) \leq M o_{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}$ .

Lemma 2.3.

[19] Let $G$ be a unicyclic graph of size $m \geq 3$ . Then $M o_{e} (G) \leq {\begin{cases} m^{2} - 2 m - 3, & if 3 \leq m \leq 8, and equality holdsiff G ≅ S_{m, 3}; \\ 60, & if m = 9, and equality holds iff G ≅ S_{m, 3}, S_{m, 4}; \\ m^{2} - m - 12, & if m \geq 10, and equality holds iff G ≅ S_{m, 4} . \end{cases}$

Lemma 2.4.

Let $G_{1}$ be a connected graph of size $m_{1}$ and $G_{2}$ be a unicyclic graph of size $m_{2}$ . Then $M o_{e} (G_{1} \cdot G_{2}) \leq {\begin{cases} M o_{e} (G_{1} \cdot S_{m_{2}, 3}) & for m_{1} + m_{2} \leq 8; \\ M o_{e} (G_{1} \cdot S_{m_{2}, 3}) = M o_{e} (G_{1} \cdot S_{m_{2}, 4}) & for m_{1} + m_{2} = 9; \\ M o_{e} (G_{1} \cdot S_{m_{2}, 4}) & for m_{1} + m_{2} \geq 10; \end{cases}$ 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} M o_{e} (G_{1} \cdot G_{2}) & = \sum_{e = u v \in E (G_{1} \cdot G_{2})} ψ_{G_{1} \cdot G_{2}} (u v) \\ = \sum_{e = u v \in E (G_{1})} ψ_{G_{1} \cdot G_{2}} (u v) + \sum_{e = u v \in E (G_{2})} ψ_{G_{1} \cdot G_{2}} (u v) \\ = \sum_{e = u v \in E (G_{1})} ψ_{G_{1} \cdot G_{2}} (u v) + M o_{e} (S_{m_{1}} \cdot G_{2}) - m_{1} (m - 1) \\ \leq \sum_{e = u v \in E (G_{1})} ψ_{G_{1} \cdot S_{m_{2}, 3}} (u v) + M o_{e} (S_{m_{1}} \cdot S_{m_{2}, 3}) - m_{1} (m - 1) \\ = \sum_{e = u v \in E (G_{1})} ψ_{G_{1} \cdot S_{m_{2}, 3}} (u v) + \sum_{e = u v \in E (S_{m_{2}, 3})} ψ_{G_{1} \cdot S_{m_{2}, 3}} (u v) \\ = M o_{e} (G_{1} \cdot S_{m_{2}, 3}) . \end{aligned}$

Similarly, if $m_{1} + m_{2} = 9$ , then $M o_{e} (G_{1} \cdot G_{2}) \leq M o_{e} (G_{1} \cdot S_{m_{2}, 3}) = M o_{e} (G_{1} \cdot S_{m_{2}, 4})$ ; if $m_{1} + m_{2} \geq 10$ , then $M o_{e} (G_{1} \cdot G_{2}) \leq M o_{e} (G_{1} \cdot S_{m_{2}, 4})$ .

3. Proof of theorem 1.2

The $Θ$ -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 $Θ (l_{1}, l_{2}, l_{3})$ .

Let $G_{m}^{1}$ represent the set of bicyclic graphs of size $m$ that contain exactly two edge-disjoint cycles. Let $G_{m}^{2}$ denote the set of bicyclic graphs of size $m$ that contain exactly three cycles. Moreover, if $G \in G_{m}^{2}$ , then $G$ contains a $Θ$ -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 $M o_{e} (G)$ on the set $G_{m}^{1}$ .

Lemma 3.1.

Let $G \in G_{m}^{1}$ . Then $M o_{e} (G) \leq {\begin{cases} m^{2} - 3 m - 6, & if 6 \leq m \leq 8, and equality holdsiff G ≅ B_{m}^{2}; \\ 48, & if m = 9, and equality holds iff G ≅ B_{m}, B_{m}^{1}, B_{m}^{2}; \\ m^{2} - m - 24, & if m \geq 10, and equality holds iff G ≅ B_{m} . \end{cases}$

Proof. Let $G \in 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} M o_{e} (G) & = M o_{e} (G_{1} \cdot G_{2}) \leq M o_{e} (G_{1} \cdot S_{m_{2}, 3}) \\ \leq M o_{e} (S_{m_{1}, 3} \cdot S_{m_{2}, 3}) = M o_{e} (B_{m}^{2}); \end{aligned}$ if $m = 9$ , then $\begin{aligned} M o_{e} (G) & = M o_{e} (G_{1} \cdot G_{2}) \leq M o_{e} (G_{1} \cdot S_{m_{2}, 3}) = M o_{e} (G_{1} \cdot S_{m_{2}, 4}) \\ \leq M o_{e} (S_{m_{1}, 3} \cdot S_{m_{2}, 3}) = M o_{e} (S_{m_{1}, 3} \cdot S_{m_{2}, 4}) = M o_{e} (B_{m}^{2}) \\ = M o_{e} (S_{m_{1}, 4} \cdot S_{m_{2}, 4}) = M o_{e} (B_{m}) = M o_{e} (B_{m}^{1}) = M o_{e} (B_{m}^{2}) . \end{aligned}$

If $m \geq 10$ , we have $\begin{aligned} M o_{e} (G) & = M o_{e} (G_{1} \cdot G_{2}) \leq M o_{e} (G_{1} \cdot S_{m_{2}, 4}) \\ \leq M o_{e} (S_{m_{1}, 4} \cdot S_{m_{2}, 4}) = M o_{e} (B_{m}) . \end{aligned}$

By simple calculation, we get $M o_{e} (B_{m}) = m^{2} - m - 24$ , $M o_{e} (B_{m}^{1}) = m^{2} - 2 m - 15$ , and $M o_{e} (B_{m}^{2}) = m^{2} - 3 m - 6$ . If $m = 9$ , then $M o_{e} (B_{m}) = M o_{e} (B_{m}^{1}) = M o_{e} (B_{m}^{2}) = 48$ . This completes the proof.

In the following, we determine a sharp upper bound for $M o_{e} (G)$ on the set $G_{m}^{2}$ .

Lemma 3.2.

Let $G \in G_{m}^{2}$ with brace $Θ (1, 2, 2)$ . Then $M o_{e} (G) \leq {\begin{cases} 4, & if m = 5, and equality holds iff G ≅ B_{m}^{3}, B_{m}^{4}; \\ m^{2} - 3 m - 6, & if 6 \leq m \leq 8, and equality holdsiff G ≅ B_{m}^{3}; \\ 48, & if m = 9, and equality holds iff G ≅ B_{m}^{3}, B_{m}^{4}; \\ m^{2} - 2 m - 15, & if m \geq 10, and equality holds iff G ≅ B_{m}^{4} . \end{cases}$

Proof. Let $G \in G_{m}^{2}$ with brace $Θ (1, 2, 2)$ . Suppose that $v_{1}, v_{2}, v_{3}, v_{4}$ be the vertices in $Θ (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} M o_{e} (G_{1}) - M o_{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) = 2 a_{2} \geq 0. \end{aligned}$

Hence, $M o_{e} (G_{1}) \geq M o_{e} (G)$ and equality holds if and only if $a_{2} = 0$ , i.e., $G ≅ 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} M o_{e} (G_{2}) - M o_{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) \\ = & 8 a_{4} \geq 0. \end{aligned}$

Hence, $M o_{e} (G_{2}) \geq M o_{e} (G_{1})$ and equality holds if and only if $a_{4} = 0$ , i.e., $G_{2} ≅ 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} M o_{e} (G_{3}) - M o_{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) \\ = & 3 a_{1} \geq 0. \end{aligned}$

Hence, $M o_{e} (G_{3}) \geq M o_{e} (G_{2})$ and equality holds if and only if $a_{1} = 0$ , i.e., $G_{3} ≅ G_{2}$ . Clearly, $G_{2} ≅ B_{m}^{3}$ with $a_{3} = 0$ , and $G_{3} ≅ B_{m}^{4}$ . Also, by simple calculation, we have $M o_{e} (B_{m}^{3}) = m^{2} - 3 m - 6$ , $M o_{e} (B_{m}^{4}) = m^{2} - 2 m - 15$ .

Lemma 3.3.

Let $G \in G_{m}^{2}$ with brace $Θ (2, 2, 2)$ . If $m \geq 6$ , then $M o_{e} (G) \leq m^{2} - m - 28$ with equality if and only if $G ≅ B_{m}^{5}$ (see Figure 2).

Proof. Let $G \in G_{m}^{2}$ with brace $Θ (2, 2, 2)$ . Let $v_{1}, v_{2}, v_{3}, v_{4}, v_{5}$ be vertices in $Θ (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} M o_{e} (G_{1}) - M o_{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) \\ = & 12 a_{2} \geq 0. \end{aligned}$

Hence, $M o_{e} (G_{1}) \geq M o_{e} (G)$ and equality holds if and only if $a_{2} = 0$ , i.e., $G ≅ 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} M o_{e} (G_{2}) - M o_{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, $M o_{e} (G_{2}) \geq M o_{e} (G_{1})$ and equality holds if and only if $a_{5} = 0$ , i.e., $G_{2} ≅ 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, $M o_{e} (G_{3}) \geq M o_{e} (G_{2})$ , and equality holds if and only if $G_{3} ≅ 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} M o_{e} (G_{4}) - M o_{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) \\ = & 6 a_{1} \geq 0. \end{aligned}$

Hence, $M o_{e} (G_{4}) \geq M o_{e} (G_{3})$ and equality holds if and only if $a_{1} = 0$ , i.e., $G_{4} ≅ G_{3}$ . Note that $G_{4} ≅ B_{m}^{5}$ . Clearly, $M o_{e} (B_{m}^{5}) = m^{2} - m - 28$ .

Lemma 3.4.

Let $G \in G_{m}^{2}$ with brace $Θ (1, 2, 3)$ . If $m \geq 6$ , then $M o_{e} (G) \leq m^{2} - 2 m - 16$ with equality if and only if $G ≅ B_{m}^{6}$ (see Figure 2).

Proof. Let $G \in G_{m}^{2}$ with brace $Θ (1, 2, 3)$ . Let $v_{1}, v_{2}, v_{3}, v_{4}, v_{5}$ be vertices in $Θ (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} M o_{e} (G_{1}) - M o_{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, $M o_{e} (G_{1}) \geq M o_{e} (G)$ and equality holds if and only if $a_{2} = a_{5} = 0$ , i.e., $G ≅ 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} M o_{e} (G_{2}) - M o_{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, $M o_{e} (G_{2}) \geq M o_{e} (G_{1})$ and equality holds if and only if $a_{4} = 0, a_{1} = a_{3}$ , i.e., $G_{2} ≅ 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} M o_{e} (G_{3}) - M o_{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) = 5 a_{3} \geq 0. \end{aligned}$

Hence, $M o_{e} (G_{3}) \geq M o_{e} (G_{2})$ and equality holds if and only if $a_{3} = 0$ , i.e., $G_{3} ≅ G_{2}$ . Note that $G_{3} ≅ B_{m}^{6}$ . Clearly, $M o_{e} (B_{m}^{6}) = m^{2} - 2 m - 16$ .

Lemma 3.5.

Let $G \in G_{m}^{2}$ with brace $Θ (a, b, c)$ . Then $M o_{e} (G) \leq {\begin{cases} 4, & if m = 5, and equality holds iff G ≅ B_{m}^{3}, B_{m}^{4}; \\ m^{2} - 3 m - 6, & if 6 \leq m \leq 8, and equality holdsiff G ≅ B_{m}^{3}; \\ 48, & if m = 9, and equality holds iff G ≅ B_{m}^{3}, B_{m}^{4}; \\ m^{2} - 2 m - 15, & if 10 \leq m \leq 12, and equalityholds iff G ≅ B_{m}^{4}; \\ 128, & if m = 13, and equality holds iff G ≅ B_{m}^{4}, B_{m}^{5}; \\ m^{2} - m - 28, & if m \geq 14, and equality holds iff G ≅ B_{m}^{5} . \end{cases}$

Proof. Suppose that $x$ and $y$ are the vertices with degree 3 in $Θ (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 $Θ (a, b, c)$ . Let $e$ be one of these six edges. Then $ψ (e) \leq m - 7$ . This property holds for the remaining five edges as well. Therefore, $M o_{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 $ψ (e_{1}) \leq m - 8$ , and $ψ (e_{2}) \leq m - 9$ . Hence, $M o_{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 $ψ (e_{1}) \leq m - 7$ , and $ψ (e_{2}) \leq m - 6$ . Hence, $M o_{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 $ψ (e_{1}) \leq m - 6$ , and $ψ (e_{2}) \leq m - 9$ . Hence, $M o_{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 $M o_{e} (B_{m}^{5}) > M o_{e} (B_{m}^{4})$ ; if $m = 13$ , then $M o_{e} (B_{m}^{3}) = M o_{e} (B_{m}^{4}) > M o_{e} (B_{m}^{5})$ ; if $10 \leq m \leq 12$ , then $M o_{e} (B_{m}^{4}) > M o_{e} (B_{m}^{5})$ ; if $m = 9$ , then $M o_{e} (B_{m}^{3}) = M o_{e} (B_{m}^{4}) > M o_{e} (B_{m}^{5})$ ; if $6 \leq m \leq 8$ , $M o_{e} (B_{m}^{3}) > M o_{e} (B_{m}^{4}) > M o_{e} (B_{m}^{5})$ ; if $m = 5$ , then $M o_{e} (B_{m}^{3}) = M o_{e} (B_{m}^{4})$ .

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} = x y$ , $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 $ψ (e_{1}) = 0$ , $ψ (e_{2}) \leq m - 5$ , and $ψ (e_{3}) \leq m - 6$ . Thus, $M o_{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} = x y$ , $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 $ψ (e_{1}) = 0$ , $ψ (e_{2}) \leq m - 4$ , $ψ (e_{2}) \leq m - 5$ , and $ψ (e_{4}) \leq m - 6$ . Hence, $M o_{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.

Acknowledgements

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).

Declarations

The authors declare no conflict of interest.

References:

Y. Alizadeh, K. Xu, and S. Klavžar. On the mostar index of trees and product graphs. Filomat, 35:4637–4643, 2021. https://doi.org/10.2298/FIL2114637A
M. Arockiaraj, J. Clement, and N. Tratnik. Mostar indices of carbon nanostructures and circumscribed donut benzenoid systems. International Journal of Quantum Chemistry, 119:26043, 2019. https://doi.org/10.1002/qua.26043
K. Deng and S. Li. Extremal catacondensed benzenoid with respect to the mostar index. Journal of Mathematical Chemistry, 58:1437–1465, 2020. https://doi.org/10.1007/s10910-020-01135-0
K. Deng and S. Li. Chemical trees with extremal mostar index. MATCH Communications in Mathematical and in Computer Chemistry, 85:161–180, 2021.
K. Deng and S. Li. On the extremal mostar indices of trees with a given segment sequence. Bulletin of the Malaysian Mathematical Sciences Society, 45:593–612, 2021. https://doi.org/10.1007/s40840-021-01208-6
K. Deng and S. Li. On the extremal values for the mostar index of trees with a given degree sequence. Applied Mathematics and Computation, 390:125598, 2021. https://doi.org/10.1016/j.amc.2020.125598
T. Došlić, I. Martinjak, R. Škrekovski, S. T. Spužević, and I. Zubac. Mostar index. Journal of Mathematical Chemistry, 56:2999–3013, 2018. https://doi.org/10.1007/s10910-018-09282-z
F. Gao, K. Xu, and T. Došlić. On the difference between mostar index and irregularity of graphs. Bulletin of the Malaysian Mathematical Sciences Society, 44:905–926, 2021. https://doi.org/10.1007/s40840-020-00991-y
A. Ghalavand, A. R. Ashrafi, and M. H. Nezhad. On mostar and edge mostar indices of graphs. Journal of Mathematics, 2021. https://doi.org/10.1155/2021/6651220
O. C. Havare. Mostar and edge mostar index for some cycle-related graphs. Romanian Journal of Mathematics and Computer Science, 10:53–66, 2020.
F. Hayat and S.-J. Xu. A lower bound on the mostar index of tricyclic graphs. Filomat, 38:6291–6297, 2024.
F. Hayat and S.-J. Xu. Extremal results on the mostar index of trees with parameters. Discrete Mathematics, Algorithms and Applications, 2024. https://doi.org/10.1142/S1793830924000253
F. Hayat and B. Zhou. On cacti with large mostar index. Filomat, 33:4865–4873, 2019. https://doi.org/10.2298/FIL1915865H
F. Hayat and B. Zhou. The mostar index of trees with parameters. Filomat, 33:6453–6458, 2019. https://doi.org/10.2298/FIL1919453H
F. Hayat, S.-J. Xu, and B. Zhou. Maximum values of the edge mostar index in tricyclic graphs. Filomat (accepted). http://dx.doi.org/10.48550/arXiv.2307.04735
S. Huang, S. Li, and M. Zhang. On the extremal mostar indices of hexagonal chains. MATCH Communications in Mathematical and in Computer Chemistry, 84:249–271, 2020.
M. Imran, S. Akhter, and Z. Iqbal. Edge mostar index of chemical structures and nanostructures using graph operations. International Journal of Quantum Chemistry, 120:e26259, 2020. https://doi.org/10.1002/qua.26259
G. Liu and K. Deng. The maximum mostar indices of unicyclic graphs with given diameter. Applied Mathematics and Computation, 439:127636, 2023. https://doi.org/10.1016/j.amc.2022.127636
H. Liu, L. Song, Q. Xiao, and Z. Tang. On edge mostar indices of graphs. Iranian Journal of Mathematical Chemistry, 11(2):95–106, 2020. https://doi.org/10.22052/ijmc.2020.221320.1489
A. Tepeh. Extremal bicyclic graphs with respect to mostar index. Applied Mathematics and Computation, 355:319–324, 2019. https://doi.org/10.1016/j.amc.2019.03.014
Q. Xiao, M. Zeng, and Z. Tang. The hexagonal chains with the first three maximal mostar indices. Discrete Applied Mathematics, 288:180–191, 2020. https://doi.org/10.1016/j.dam.2020.08.036
Q. Xiao, M. Zeng, Z. Tang, H. Deng, and H. Hua. Hexagonal chains with first three minimal mostar indices. MATCH Communications in Mathematical and in Computer Chemistry, 85:47–61, 2021.

[1] Y. Alizadeh, K. Xu, and S. Klavžar. On the mostar index of trees and product graphs. Filomat, 35:4637–4643, 2021. https://doi.org/10.2298/FIL2114637A

[2] M. Arockiaraj, J. Clement, and N. Tratnik. Mostar indices of carbon nanostructures and circumscribed donut benzenoid systems. International Journal of Quantum Chemistry, 119:26043, 2019. https://doi.org/10.1002/qua.26043

[3] K. Deng and S. Li. Extremal catacondensed benzenoid with respect to the mostar index. Journal of Mathematical Chemistry, 58:1437–1465, 2020. https://doi.org/10.1007/s10910-020-01135-0

[4] K. Deng and S. Li. Chemical trees with extremal mostar index. MATCH Communications in Mathematical and in Computer Chemistry, 85:161–180, 2021.

[5] K. Deng and S. Li. On the extremal mostar indices of trees with a given segment sequence. Bulletin of the Malaysian Mathematical Sciences Society, 45:593–612, 2021. https://doi.org/10.1007/s40840-021-01208-6

[6] K. Deng and S. Li. On the extremal values for the mostar index of trees with a given degree sequence. Applied Mathematics and Computation, 390:125598, 2021. https://doi.org/10.1016/j.amc.2020.125598

[7] T. Došlić, I. Martinjak, R. Škrekovski, S. T. Spužević, and I. Zubac. Mostar index. Journal of Mathematical Chemistry, 56:2999–3013, 2018. https://doi.org/10.1007/s10910-018-09282-z

[8] F. Gao, K. Xu, and T. Došlić. On the difference between mostar index and irregularity of graphs. Bulletin of the Malaysian Mathematical Sciences Society, 44:905–926, 2021. https://doi.org/10.1007/s40840-020-00991-y

[9] A. Ghalavand, A. R. Ashrafi, and M. H. Nezhad. On mostar and edge mostar indices of graphs. Journal of Mathematics, 2021. https://doi.org/10.1155/2021/6651220

[10] O. C. Havare. Mostar and edge mostar index for some cycle-related graphs. Romanian Journal of Mathematics and Computer Science, 10:53–66, 2020.

[11] F. Hayat and S.-J. Xu. A lower bound on the mostar index of tricyclic graphs. Filomat, 38:6291–6297, 2024.

[12] F. Hayat and S.-J. Xu. Extremal results on the mostar index of trees with parameters. Discrete Mathematics, Algorithms and Applications, 2024. https://doi.org/10.1142/S1793830924000253

[13] F. Hayat and B. Zhou. On cacti with large mostar index. Filomat, 33:4865–4873, 2019. https://doi.org/10.2298/FIL1915865H

[14] F. Hayat and B. Zhou. The mostar index of trees with parameters. Filomat, 33:6453–6458, 2019. https://doi.org/10.2298/FIL1919453H

[15] F. Hayat, S.-J. Xu, and B. Zhou. Maximum values of the edge mostar index in tricyclic graphs. Filomat (accepted). http://dx.doi.org/10.48550/arXiv.2307.04735

[16] S. Huang, S. Li, and M. Zhang. On the extremal mostar indices of hexagonal chains. MATCH Communications in Mathematical and in Computer Chemistry, 84:249–271, 2020.

[17] M. Imran, S. Akhter, and Z. Iqbal. Edge mostar index of chemical structures and nanostructures using graph operations. International Journal of Quantum Chemistry, 120:e26259, 2020. https://doi.org/10.1002/qua.26259

[18] G. Liu and K. Deng. The maximum mostar indices of unicyclic graphs with given diameter. Applied Mathematics and Computation, 439:127636, 2023. https://doi.org/10.1016/j.amc.2022.127636

[19] H. Liu, L. Song, Q. Xiao, and Z. Tang. On edge mostar indices of graphs. Iranian Journal of Mathematical Chemistry, 11(2):95–106, 2020. https://doi.org/10.22052/ijmc.2020.221320.1489

[20] A. Tepeh. Extremal bicyclic graphs with respect to mostar index. Applied Mathematics and Computation, 355:319–324, 2019. https://doi.org/10.1016/j.amc.2019.03.014

[21] Q. Xiao, M. Zeng, and Z. Tang. The hexagonal chains with the first three maximal mostar indices. Discrete Applied Mathematics, 288:180–191, 2020. https://doi.org/10.1016/j.dam.2020.08.036

[22] Q. Xiao, M. Zeng, Z. Tang, H. Deng, and H. Hua. Hexagonal chains with first three minimal mostar indices. MATCH Communications in Mathematical and in Computer Chemistry, 85:47–61, 2021.

Contents

Utilitas Mathematica

Disproof of a conjecture on the edge mostar index

Abstract

1. Introduction

2. Preliminaries

3. Proof of theorem 1.2

Acknowledgements

Declarations

References:

Information

Guidelines

CP Initiatives

Follow CP