University of Primorska
Faculty of Mathematics, Natural Sciences and Information Technologies
Datum / Date: 22.3.21
Čas / Time: 10:00 — 11:00
Predavalnica / Location: Zoom
Predavatelj / Lecturer: Dieter Rautenbach (Ulm University, Germany)
Naslov / Title: Distance-unbalancedness of trees
Povzetek / Abstract:
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
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.