Maximally distance-unbalanced trees

DOI10.1007/S10910-021-01287-7zbMATH Open1480.92244arXiv2103.04684OpenAlexW3197691496MaRDI QIDQ2065663FDOQ2065663

Authors: Marie Kramer, Dieter Rautenbach 

Publication date: 12 January 2022

Published in: Journal of Mathematical Chemistry (Search for Journal in Brave)

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 $muB(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 $muB(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, Journal of Mathematical Chemistry, DOI 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 Miklaviv{c} and v{S}parl, we show ${\displaystyle }$maxBig{{ m uB}(T):Tmbox{ is a tree of order }nBig} =frac{n^3}{2}+o(n^3)${\displaystyle }$ and ${\displaystyle }$maxBig{{ m uB}(S(n_1,ldots,n_k)):1+n_1+cdots+n_k=nBig} =left(frac{1}{2}-frac{5}{6k}+frac{1}{3k^2} ight)n^3+O(kn^2),${\displaystyle }$ where $S(n_1,ldots,n_k)$ is the subdivided star such that removing its center vertex leaves paths of orders $n_1,ldots,n_k$.

Full work available at URL: https://arxiv.org/abs/2103.04684

Recommendations

• Minimum distance-unbalancedness of trees
• Distance-unbalancedness of graphs
• Minimum distance-unbalancedness of graphs with diameter 2 and given number of edges
• Maximizing distance between center, centroid and subtree core of trees
• Different central parts of trees and their pairwise distances

zbMATH Keywords

Mostar indexdistance-balanced graphdistance-unbalancedness

Mathematics Subject Classification ID

Graphical indices (Wiener index, Zagreb index, Randi? index, etc.) (05C09) Molecular structure (graph-theoretic methods, methods of differential topology, etc.) (92E10) Chemical graph theory (05C92)

Cites Work

• Bipartite graphs with balanced \((a,b)\)-partitions
• \(\ell\)-distance-balanced graphs
• Distance-balanced graphs
• Mostar index
• Minimum distance-unbalancedness of trees

Cited In (3)

• Unbalanced subtrees in binary rooted ordered and un-ordered trees
• Minimum Distance-Unbalancedness of Graphs With Diameter 2 and Given Number of Edges
• Peripherality in networks: theory and applications

This page was built for publication: Maximally distance-unbalanced trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2065663)