| dc.description.abstract | Parking functions have been a focus of mathematical research since the mid-1970s.
Various generalizations have been introduced since the mid-1990s and deep relationships
between these and other areas of mathematics have been discovered. Here, we
introduced a new generalization, the G-multiparking function, where G is a simple
graph on a totally ordered vertex set {1, 2, . . . , n}. We give an algorithm that converts
a G-multiparking function into a rooted spanning forest of G by using a graph
searching technique to build a sequence F1, F2, . . . , Fn, where each Fi is a subforest of
G and Fn is a spanning forest of G. We also give another algorithm that converts a
rooted spanning forest of G to a G-multiparking function and prove that the resulting
functions (between the sets of G-multiparking functions and rooted spanning forests
of G) are bijections and inverses of each other. Each of these two algorithms relies
on a choice function , which is a function from the set of pairs (F,W) (where F is
a subforest of G and W is a set of some of the leaves of F) into W. There are many
possible choice functions for a given graph, each giving formality to the concept of
choosing how a graph searching algorithm should procede at each step (i.e. if the algorithm
has reached Fi, then Fi+1 is some forest on the vertex set V (Fi)∪{(Fi,W)}
for some W).
We also define F-redundant edges, which are edges whose removal from G does
not affect the execution of either algorithm mentioned above. This concept leads to a categorization of the edges of G, which in turn provides a new formula for the Tutte
polynomial of G and other enumerative results. | en |
