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.
Original language | English |
---|---|
Article number | 112255 |
Journal | Discrete Mathematics |
Volume | 344 |
Issue number | 3 |
DOIs | |
Publication status | Published - Mar 2021 |
Keywords
- chromatic symmetric function
- graph polynomials
- rooted trees
- tree distinguishing conjecture
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics