Univerza na Primorskem
Fakulteta za matematiko, naravoslovje in informacijske tehnologije
2021-03-22
10:00 — 11:00
Zoom
Dieter Rautenbach (Ulm University, Germany)
Distance-unbalancedness of trees
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. Miklaviv{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 Miklaviv{c} and v{S}parl, we show that stars minimize distance-unbalancedness among all trees of a given order, that
max{{uB}(T):T is a tree of order n}=n3/2 +o(n3)
and that
max{uB}(S(n1,…,nk)):1+n1+⋯+nk=n}=(1/2 -5/6k +1/3k2 )n3+O(kn2),
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.