Minimum distance-unbalancedness of trees

Abstract: 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

. Miklaviv{c} and v{S}parl (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.

Recommendations

Cites work

Cited in

(6)

This page was built for publication: Minimum distance-unbalancedness of trees