A tree distinguishing polynomial

DOI10.48550/ARXIV.1904.03332MaRDI QIDQ106322zbMATH OpenOpenAlexFDO

Authors Pengyu Liu, Mona Azadkia

Publication date 6 April 2019

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

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

zbMATH Keywords

graph polynomialisomorphism invarianttrees

Mathematics Subject Classification ID

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

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.

Recommendations

• Tutte polynomials for trees
• Indistinguishable trees and graphs
• Polychromatic polynomials
• On the smallest trees with the same restricted \(U\)-polynomial and the rooted \(U\)-polynomial
• scientific article; zbMATH DE number 1185324

Cites work

• scientific article; zbMATH DE number 1033559 (Why is no real title available?)
• scientific article; zbMATH DE number 791397 (Why is no real title available?)
• scientific article; zbMATH DE number 850224 (Why is no real title available?)
• A Contribution to the Theory of Chromatic Polynomials
• A new polynomial invariant of knots and links
• A polynomial invariant for knots via von Neumann algebras
• A symmetric function generalization of the chromatic polynomial of a graph
• A weighted graph polynomial from chromatic invariants of knots
• Factoring multivariate polynomials with many factors and huge coefficients
• Intersection theory for graphs
• Isomorphism of weighted trees and Stanley's isomorphism conjecture for caterpillars
• Multidimensional scaling. I: Theory and method
• On distinguishing trees by their chromatic symmetric functions
• On trees with the same restricted \(U\)-polynomial and the Prouhet-Tarry-Escott problem
• Polychromatic polynomials
• Polynomial invariants of graphs. II
• The bivariate Ising polynomial of a graph
• The equivalence of two graph polynomials and a symmetric function
• The polychromate and a chord diagram polynomial
• Tutte polynomials for trees

Cited in

(14)

• Polynomial invariants for rooted trees related to their random destruction
• HOW TO COUNT TREES?
• Almost all trees share a complete set of immanantal polynomials
• scientific article; zbMATH DE number 1185324 (Why is no real title available?)
• Polynomial invariants for cactuses
• Indistinguishable trees and graphs
• On the smallest trees with the same restricted \(U\)-polynomial and the rooted \(U\)-polynomial
• Disposition polynomials and plane trees
• Tutte polynomials for trees
• Ranking trees based on global centrality measures
• treenomial
• scientific article; zbMATH DE number 7583268 (Why is no real title available?)
• On graphs with the same restricted \(U\)-polynomial and the \(U\)-polynomial for rooted graphs
• Tree enumeration polynomials on separable permutations

This page was built for publication: A tree distinguishing polynomial

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q106322)