Maximizing distance between center, centroid and subtree core of trees

Proceedings of the Indian Academy of Sciences. Mathematical sciences

KAMAL LOCHAN PATRA^1,2¹  DHEER NOAL SUNIL DESAI^1,2² 

[1] Homi Bhabha National Institute (HBNI), Training School Complex, Anushakti Nagar, Mumbai 400 094, India^2;School of Mathematical Sciences, National Institute of Science Education and Research (NISER), Bhubaneswar P.O. – Jatni, District – Khurda, Odisha 752 050, India^1

关键词: Tree;    center;    centroid;    subtree core;    distance;   

DOI  :  

学科分类：数学（综合）

来源: Indian Academy of Sciences

【 摘 要 】

For $n \geq 5$ and $2 \leq g \leq n−3$, consider the tree $P_{n−g,g}$ on $n$ vertices which is obtained by adding $g$ pendant vertices to one end vertex of the path $P_{n−g}$. We call the trees $P_{n−g,g}$ as path-star trees. The subtree core of a tree $T$ is the set of all vertices $v$ of $T$ for which the number of subtrees of $T$ containing $v$ is maximum. We prove that over all trees on $n \geq 5$ vertices, the distance between the center (respectively, centroid) and the subtree core is maximized by some path-star trees. We also prove that the tree $P_{n−g0,g0}$ maximizes both the distances among all path-star trees on $n$ vertices, where $g0$ is the smallest positive integer satisfying $2^{g0} + g0$ > $n − 1$.

【 授权许可】

CC BY