Bounding the Mostar index

Abstract

Došlić et al. defined the Mostar index of a graph $G$ as $Mo(G)=\sum _{uv\in E(G)}|n_G(u,v)-n_G(v,u)|$, where, for an edge $uv$ of $G$, the term $n_G(u,v)$ denotes the number of vertices of $G$ that have a smaller distance in $G$ to $u$ than to $v$. They conjectured that $Mo(G)\le 0.\overline{148}{n}^3$ for every graph $G$ of order $n$. As a natural upper bound on the Mostar index, Geneson and Tsai implicitly consider the parameter $M{o}^{\star }(G)=\sum _{uv\in E(G)}(n-\min \{d_G(u),d_G(v)\})$. For a graph $G$ of order $n$, they show that $M{o}^{\star }(G)\le \frac{5}{24}(1+o(1))n^3$. We improve this bound to $M{o}^{\star }(G)\le \left(\frac{2}{\sqrt{3}}-1\right)n^3$, which is best possible up to terms of lower order. Furthermore, we show that $M{o}^{\star }(G)\le \left(2{\left(\frac{\Delta }{n}\right)}^2+\left(\frac{\Delta }{n}\right)-2\left(\frac{\Delta }{n}\right)\sqrt{{\left(\frac{\Delta }{n}\right)}^2+\left(\frac{\Delta }{n}\right)}\right)n^3$ provided that $G$ has maximum degree $\Delta$.