Štefko Miklavič: Bounding the Mostar index

Došlić et al. defined the Mostar index of a graph G as ∑_{uv ∈ 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 are closer to u than to v. They also conjectured that Mostar index of G, Mo(G), is less or equal to 0.148 n³. In this talk we show that Mo(G) ≤ 0.1633 n³. If, however, G is bipartite, then we show that Mo(G) ≤ √3/18 n³, and that this bound is best possible up to terms of order O(n²).

This is joint work with Johannes Pardey, Dieter Rautenbach and Florian Werner from Ulm University.

Join Zoom Meeting HERE!