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