A tree distinguishing polynomial

DOI10.48550/ARXIV.1904.03332zbMATH Open1451.05121arXiv1904.03332OpenAlexW3081157667MaRDI QIDQ106322FDOQ106322

Authors: 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

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

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)

Cites Work

• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Contribution to the Theory of Chromatic Polynomials
• The bivariate Ising polynomial of a graph

Cited In (14)

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

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)