For a graph G, and two distinct vertices u and v of G, let nG(u,v) be the number of vertices of G that are closer in G to u than to v. Miklavi\v{c} and \v{S}parl (arXiv:2011.01635v1) define the distance-unbalancedness {uB}(G) of G as the sum of |nG(u,v)-nG(v,u)| over all unordered pairs of distinct vertices u and v of G. For positive integers n up to 15, they determine the trees T of fixed order n with the smallest and the largest values of { uB}(T), respectively. While the smallest value is achieved by the star K1,n-1 for these n, the structure of the trees maximizing the distance-unbalancedness remained unclear. For n up to 15 at least, all these trees were subdivided stars. Contributing to problems posed by Miklavi\v{c} and \v{S}parl, we show that stars minimize distance-unbalancedness among all trees of a given order, that
and that
where S(n1,…,nk) is the subdivided star such that removing its center vertex leaves paths of orders n1,…,nk.
Join Zoom Meeting HERE!
See you there!
Everyone is welcome and encouraged to attend.
For more info visit our YouTube Channel.