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.