Skip to Main Content

Proceedings of the American Mathematical Society

Published by the American Mathematical Society, the Proceedings of the American Mathematical Society (PROC) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Proceedings of the American Mathematical Society is 0.85.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

A greedoid polynomial which distinguishes rooted arborescences
HTML articles powered by AMS MathViewer

by Gary Gordon and Elizabeth McMahon PDF
Proc. Amer. Math. Soc. 107 (1989), 287-298 Request permission

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
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
  • © Copyright 1989 American Mathematical Society
  • 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