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.
| Identifer | oai:union.ndltd.org:tamu.edu/oai:repository.tamu.edu:1969.1/ETD-TAMU-1549 |
| Date | 15 May 2009 |
| Creators | Kostic, Dimitrije Nenad |
| Contributors | Yan, Catherine H. |
| Source Sets | Texas A and M University |
| Language | en_US |
| Detected Language | English |
| Type | Book, Thesis, Electronic Dissertation, text |
| Format | electronic, application/pdf, born digital |
Page generated in 0.0013 seconds