Line Trees

One utility that is useful in certain applications is the ability to create `line trees'. That is a tree consisting of $n$ vertices $(v_0, v_1, \ldots, v_{n-1})$in which vertex $v_0$ is adjacent to $v_1$, $v_{n-1}$ is adjacent to $v_{n-2}$ and every other vertex $v_k$ in the tree is adjacent to $v_{k-1}$ and $v_{k+1}$. We will denote such a tree as $\mathit{Line}(n)$. (Note that any tree of the form $\mathit{Line}(n)$ is a path of length $n-1$.) Of course, many adjacency matrices would correspond to `line trees', but this method of genration yields adjacency matrices which have adjacencies in a `diagonal', e.g.:

$$\left[ \begin{array}{ccccccc} 0 & 1 & 0 & 0 & 0 & 0 & \cdo... ...ots & \vdots & \vdots & \vdots & \ddots \\ \end{array}\right]$$