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

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Article number112255
JournalDiscrete Mathematics
Volume344
Issue number3
DOIs
Publication statusPublished - Mar 2021

Keywords

  • chromatic symmetric function
  • graph polynomials
  • rooted trees
  • tree distinguishing conjecture

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'On the smallest trees with the same restricted U-polynomial and the rooted U-polynomial'. Together they form a unique fingerprint.

Cite this