A polynomial associated with rooted trees and specific posets

DOI10.22108/TOC.2022.130043.1895zbMATH Open1513.05210arXiv1803.09623MaRDI QIDQ6299595FDOQ6299595

Authors: Valisoa Razanajatovo Misanantenaina, Stephan Wagner 

Publication date: 26 March 2018

Abstract: We investigate a trivariate polynomial associated with rooted trees. It generalises a bivariate polynomial for rooted trees that was recently introduced by Liu. We show that this polynomial satisfies a deletion-contraction recursion and can be expressed as a sum over maximal antichains. Several combinatorial quantities can be obtained as special values, in particular the number of antichains, maximal antichains and cutsets. We prove that two of the three possible bivariate specialisations characterise trees uniquely up to isomorphism. One of these has already been established by Liu, the other is new. For the third specialisation, we construct non-isomorphic trees with the same associated polynomial. We finally find that our polynomial can be generalised in a natural way to a family of posets that we call $mathcalV$-posets. These posets are obtained recursively by either disjoint unions or adding a greatest/least element to existing $mathcalV$-posets.

Mathematics Subject Classification ID

Trees (05C05) Graph polynomials (05C31) Combinatorics of partially ordered sets (06A07)

This page was built for publication: A polynomial associated with rooted trees and specific posets

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