Graph searching and a generalized parking function
| dc.contributor | Yan, Catherine H. | |
| dc.creator | Kostic, Dimitrije Nenad | |
| dc.date.accessioned | 2010-01-15T00:02:26Z | |
| dc.date.accessioned | 2010-01-16T01:54:32Z | |
| dc.date.accessioned | 2017-04-07T19:56:31Z | |
| dc.date.available | 2010-01-15T00:02:26Z | |
| dc.date.available | 2010-01-16T01:54:32Z | |
| dc.date.available | 2017-04-07T19:56:31Z | |
| dc.date.created | 2007-08 | |
| dc.date.issued | 2009-05-15 | |
| 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. | |
| dc.identifier.uri | http://hdl.handle.net/1969.1/ETD-TAMU-1549 | |
| dc.language.iso | en_US | |
| dc.subject | combinatorics | |
| dc.subject | parking functions | |
| dc.subject | algorithms | |
| dc.title | Graph searching and a generalized parking function | |
| dc.type | Book | |
| dc.type | Thesis |