dc.contributor.advisor 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.available 2010-01-15T00:02:26Z dc.date.available 2010-01-16T01:54:32Z dc.date.created 2007-08 dc.date.issued 2009-05-15 dc.identifier.uri http://hdl.handle.net/1969.1/ETD-TAMU-1549 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 dc.format.medium electronic en dc.format.mimetype application/pdf dc.language.iso en_US dc.subject combinatorics en dc.subject parking functions en dc.subject algorithms en dc.title Graph searching and a generalized parking function en dc.type Book en dc.type Thesis en thesis.degree.department Mathematics en thesis.degree.discipline Mathematics en thesis.degree.grantor Texas A&M University en thesis.degree.name Doctor of Philosophy en thesis.degree.level Doctoral en dc.contributor.committeeMember Aguiar, Marcelo dc.contributor.committeeMember Chen, Jianer dc.contributor.committeeMember Rojas, Maurice dc.contributor.committeeMember Schenck, Henry dc.contributor.committeeMember Tretkoff, Paula dc.type.genre Electronic Dissertation en dc.type.material text en dc.format.digitalOrigin born digital en
﻿