Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



A greedoid polynomial which distinguishes rooted arborescences

Authors: Gary Gordon and Elizabeth McMahon
Journal: Proc. Amer. Math. Soc. 107 (1989), 287-298
MSC: Primary 05B35; Secondary 05C20
MathSciNet review: 967486
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We define a two-variable polynomial ${f_G}(t,z)$ for a greedoid $G$ which generalizes the standard one-variable greedoid polynomial ${\lambda _G}(t)$. Several greedoid invariants (including the number of feasible sets, bases, and spanning sets) are easily shown to be evaluations of ${f_G}(t,z)$. We prove (Theorem 2.8) that when $G$ is a rooted directed arborescence, ${f_G}(t,z)$ completely determines the arborescence. We also show the polynomial is irreducible over ${\mathbf {Z}}[t,z]$ for arborescences with only one edge directed out of the distinguished vertex. When $G$ is a matroid, ${f_G}(t,z)$ coincides with the Tutte polynomial. We also give an example to show Theorem 2.8 fails for full greedoids. This example also shows ${f_G}(t,z)$ does not distinguish rooted arborescences among the class of all greedoids.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 05B35, 05C20

Retrieve articles in all journals with MSC: 05B35, 05C20

Additional Information

Keywords: Greedoid, rooted digraph, arborescence
Article copyright: © Copyright 1989 American Mathematical Society