On the smallest trees with the same restricted U-polynomial and the rooted U-polynomial

Abstract In this article, we construct explicit examples of pairs of non-isomorphic trees with the same restricted U -polynomial for every k ; by this we mean that the polynomials agree on terms with degree at most k + 1 . The main tool for this construction is a generalization of the U -polynomial to rooted graphs, which we introduce and study in this article. Most notably we show that rooted trees can be reconstructed from its rooted U -polynomial.