On the distances between the core center and other central parts of a tree

Abstract

Let $T$ be a tree. For a vertex $v\in V(T)$, the eccentric subtree number ${\epsilon }_T(v)$ is defined as ${\epsilon }_T(v)=\min \{f_T(v,u):u\in V(T)\}$ where $f_T(v,u)$ denotes the number of subtrees of $T$ containing both $v$ and $u$. A core vertex of $T$ is a vertex with the maximum eccentric subtree number, and the set of all the core vertices of $T$ is called the core center of $T$. The core center of $T$ consists of either a single vertex or two adjacent vertices. There are other central concepts in a tree, such as the center, centroid, subtree core, and characteristic center, and these may all be different. By $d_T(C,\mathfrak{C})$, $d_T(C_d,\mathfrak{C})$ and $d_T(S_c,\mathfrak{C})$ we mean the distance between center and core center, distance between centroid and core center and distance between subtree core and core center in $T$, respectively. We show that for any tree $T$ on $n\ge 6$ vertices, (i)]$d_T(C,\mathfrak{C})\le \lfloor \frac{n-g_0-4}{2}\rfloor$; (ii)]$d_T(C_d,\mathfrak{C})\le \lfloor \frac{n-5}{2}\rfloor$; (iii)] $d_T(S_c,\mathfrak{C})\leq\left\{ \begin{array}{ll} 1, &\text{if $n=7$,} n-g_0-3, &\text{if $n\neq 7$;}\\ \end{array} \right.$ where $g_0\ge 2$ be the smallest positive integer such that $2^{g_0-1}+g_0\ge n-3$. Moreover, we show that these bounds are best possible by obtaining a tree which attains these bounds. We also obtain a tree which maximizes the distance between characteristic center and core center over all trees on $n\ge 6$ vertices. The asymptotic behaviour of all these distances are also studied.

20 pages, 3 figures