Minimum distance-unbalancedness of trees

摘要

For a graph G, and two distinct vertices u and v of G, let n(G)(u, v) be the number of vertices of G that are closer in G to u than to v. Miklavic and Sparl (arXiv:2011.01635v1) define the distance-unbalancedness of G as the sum of [n(G)(u, v) - n(G)(v, u)] over all unordered pairs of distinct vertices u and v of G. Confirming one of their conjectures, we show that the stars minimize the distance-unbalancedness among all trees of a fixed order.