Mostar index and bounded maximum degree

Michael A. Henning, Johannes Pardey, Dieter Rautenbach, Florian Werner

Research output: Contribution to journalArticlepeer-review

Abstract

Došlić et al. defined the Mostar index of a graph G as Mo(G)=∑uv∈E(G)|nG(u,v)−nG(v,u)|, where, for an edge uv of G, the term nG(u,v) denotes the number of vertices of G that have a smaller distance in G to u than to v. For a graph G of order n and maximum degree at most Δ, we show [Formula presented] where cΔ>0 only depends on Δ and the o(1) term only depends on n. Furthermore, for integers n0 and Δ at least 3, we show the existence of a Δ-regular graph of order n at least n0 with [Formula presented] where cΔ>0 only depends on Δ.

Original languageEnglish
Article number100861
JournalDiscrete Optimization
Volume54
DOIs
Publication statusPublished - Nov 2024

Keywords

  • Mostar index

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Mostar index and bounded maximum degree'. Together they form a unique fingerprint.

Cite this