A Tutte-like polynomial for rooted trees and specific posets
2018
We investigate a Tutte-like polynomial for rooted trees and posets called $\mathcal{V}$-posets. These posets are obtained recursively by either disjoint unions or adding a greatest/least element to existing $\mathcal{V}$-posets, and they can also be characterised as those posets that do not contain an $N$-poset or a bowtie as induced subposets. We show that our polynomials satisfy a deletion-contraction recursion and can be expressed as a sum over maximal antichains. We find that our polynomials yield the number of antichains, maximal antichains and cutsets (transversals) as special values. We conclude this paper by enumerating $\mathcal{V}$-posets by means of generating functions and by determining an asymptotic formula for the number of $n$-element $\mathcal{V}$-posets.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
15
References
2
Citations
NaN
KQI