UP - logo
E-viri
Recenzirano Odprti dostop
  • Maximally distance-unbalanc...
    Kramer, Marie; Rautenbach, Dieter

    Journal of mathematical chemistry, 11/2021, Letnik: 59, Številka: 10
    Journal Article

    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 . Miklavič and Šparl ( arXiv:2011.01635v1 ) define the distance-unbalancedness uB ( G ) 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 . 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 K 1 , n - 1 for these n , which we then proved for general n (Minimum distance-unbalancedness of trees, J Math Chem, https://doi.org/10.1007/s10910-021-01228-4 ), 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č and Šparl, we show max { uB ( T ) : T is a tree of order n } = n 3 2 + o ( n 3 ) and max { uB ( S ( n 1 , … , n k ) ) : 1 + n 1 + ⋯ + n k = n } = 1 2 - 5 6 k + 1 3 k 2 n 3 + O ( k n 2 ) , where S ( n 1 , … , n k ) is the subdivided star such that removing its center vertex leaves paths of orders n 1 , … , n k .