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
DOI: https://doi.org/10.1090/S0002-9939-1989-0967486-0
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

DOI: https://doi.org/10.1090/S0002-9939-1989-0967486-0
Keywords: Greedoid, rooted digraph, arborescence
Article copyright: © Copyright 1989 American Mathematical Society