Minimum distance-unbalancedness of trees

2021 
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.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    6
    References
    4
    Citations
    NaN
    KQI
    []