Polynomial invariants for rooted trees related to their random destruction

Fabian Burghart¹

¹Eindhoven University of Technology

The electronic journal of combinatorics, Tome 31 (2024) no. 4

Résumé

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$.

Détail

DOI : 10.37236/11975

Classification : 05C31, 05C05, 60C05
Mots-clés : random destruction processes, random cutting model, site percolation on rooted trees