Polynomial Invariants for Rooted Trees Related to Their Random Destruction

We consider three bivariate polynomial invariants $P$, $A$, and $S$ for rooted trees, as well as a trivariate polynomial invariant $M$. These invariants are motivated by random destruction processes such as the random cutting model or site percolation on rooted trees. We exhibit recursion formulas f...

Full description

Saved in:
Bibliographic Details
Published in:The Electronic journal of combinatorics 2024-11, Vol.31 (4)
Main Author: Burghart, Fabian
Format: Article
Language:English
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider three bivariate polynomial invariants $P$, $A$, and $S$ for rooted trees, as well as a trivariate polynomial invariant $M$. These invariants are motivated by random destruction processes such as the random cutting model or site percolation on rooted trees. We exhibit recursion formulas for the invariants and identities relating $P$, $S$, and $M$. The main result states that the invariants $P$ and $S$ are complete, that is they distinguish rooted trees (in fact, even rooted forests) up to isomorphism. The proof method relies on the obtained recursion formulas and on irreducibility of the polynomials in suitable unique factorization domains. For $A$, we provide counterexamples showing that it is not complete, although that question remains open for the trivariate invariant $M$.
ISSN:1077-8926
1077-8926
DOI:10.37236/11975