Reconstructing Trees from their
Wiener Matrix or Subtree Matrix
Meeting Time: Oct. 12, 2010, 2:00-2:50pm
Abstract:
Let $T$ be a tree with vertex set $\{1,2,\ldots,n\}$. The Wiener matrix is
$W=(w_{ij})$ where $w_{ij}$ ($i\ne j$) is the number of paths in $T$
containing both $i$ and $j$. The subtree matrix is $S=(s_{ij})$ where
$s_{ij}$ ($i\ne j$) is the number of subtrees of $T$ containing both $i$
and $j$. In both $W$ and $S$ the diagonal entries are $0$. Given either of
these matrices we will show that we can reconstruct the adjacencies of $T$
using the following simple rule: $i\sim j$ in $T$ if and only if the
$(i,j)$-th entry of the matrix is the largest in its row or column.