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\geq 6$ vertices,
(i)]$d_T(C,\mathfrak{C})\leq \lfloor \frac{n-g_0-4}{2} \rfloor$;
(ii)]$d_T(C_d,\mathfrak{C})\leq \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\geq 2$ be the smallest positive integer such that $2^{g_0-1}+g_0\geq 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\geq 6$ vertices. The asymptotic behaviour of all these distances are also studied.
이 뉴스, 어떠셨어요?
탭 한 번으로 반응 · 로그인 불필요