A tree distinguishing polynomial

DOI10.48550/ARXIV.1904.03332zbMath1451.05121arXiv1904.03332OpenAlexW3081157667MaRDI QIDQ106322

Pengyu Liu, Mona Azadkia

Publication date: 6 April 2019

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: We define a bivariate polynomial for unlabeled rooted trees and show that the polynomial of an unlabeled rooted tree $T$ is the generating function of a class of subtrees of $T$. We prove that the polynomial is a complete isomorphism invariant for unlabeled rooted trees. Then, we generalize the polynomial to unlabeled unrooted trees and we show that the generalized polynomial is a complete isomorphism invariant for unlabeled unrooted trees.

Full work available at URL: https://arxiv.org/abs/1904.03332

zbMATH Keywords

treesgraph polynomialisomorphism invariant

Mathematics Subject Classification ID

Trees (05C05) Graph polynomials (05C31) Exact enumeration problems, generating functions (05A15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The bivariate Ising polynomial of a graph
• Intersection theory for graphs
• A weighted graph polynomial from chromatic invariants of knots
• Polychromatic polynomials
• The polychromate and a chord diagram polynomial
• Factoring multivariate polynomials with many factors and huge coefficients
• A symmetric function generalization of the chromatic polynomial of a graph
• Polynomial invariants of graphs. II
• Isomorphism of weighted trees and Stanley's isomorphism conjecture for caterpillars
• On trees with the same restricted \(U\)-polynomial and the Prouhet-Tarry-Escott problem
• On distinguishing trees by their chromatic symmetric functions
• Multidimensional scaling. I: Theory and method
• The Equivalence of Two Graph Polynomials and a Symmetric Function
• A polynomial invariant for knots via von Neumann algebras
• A new polynomial invariant of knots and links
• Tutte polynomials for trees
• A Contribution to the Theory of Chromatic Polynomials

Related Items (5)

Ranking trees based on global centrality measures ⋮ Polynomial invariants for cactuses ⋮ treenomial ⋮ Unnamed Item ⋮ Polynomial invariants for rooted trees related to their random destruction

This page was built for publication: A tree distinguishing polynomial