تعداد نشریات | 43 |
تعداد شمارهها | 1,386 |
تعداد مقالات | 11,416 |
تعداد مشاهده مقاله | 18,684,518 |
تعداد دریافت فایل اصل مقاله | 8,982,550 |
A polynomial associated with rooted trees and specific posets | ||
Transactions on Combinatorics | ||
مقاله 7، دوره 11، شماره 3، آذر 2022، صفحه 255-279 اصل مقاله (538.23 K) | ||
نوع مقاله: Workshop on Graphs, Topology and Topological Groups, Cape Town, South Africa | ||
شناسه دیجیتال (DOI): 10.22108/toc.2022.130043.1895 | ||
نویسندگان | ||
Valisoa Razanajatovo Misanantenaina1؛ Stephan Wagner ![]() | ||
1Department of Logistics, Stellenbosch University, Private Bag X1, Matieland 7602, South Africa | ||
2Department of Mathematics, Uppsala Universitet, Box 480, 751 06 Uppsala, Sweden | ||
چکیده | ||
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 Ѵ-posets. These posets are obtained recursively by either disjoint unions or adding a greatest/least element to existing Ѵ-posets. | ||
کلیدواژهها | ||
Rooted trees؛ polynomials؛ antichains؛ cutsets؛ posets | ||
آمار تعداد مشاهده مقاله: 76 تعداد دریافت فایل اصل مقاله: 43 |