On the Diameter of $n$th Order Degree Regular Trees

Abstract

For $n$ a positive integer and $v$ a vertex of a graph $G$, the $n$th order degree of $v$ in $G$, denoted by ${\text{deg}}_n(v)$, is the number of vertices at distance $n$ from $v$. The graph $G$ is said to be $n$th order regular of degree $k$ if, for every vertex $v$ of $G$, ${\text{deg}}_n(v)=k$. For $n\in \{7,8,\dots ,11\}$, a characterization of $n$th order regular trees of degree $2$ is obtained. It is shown that, for $n\ge 2$ and $k\in \{3,4,5\}$, if $G$ is an $n$th order regular tree of degree $k$, then $G$ has diameter $2n–1$.