Show simple item record

dc.contributor.advisorYan, Catherine H.
dc.creatorKostic, Dimitrije Nenad
dc.date.accessioned2010-01-15T00:02:26Z
dc.date.accessioned2010-01-16T01:54:32Z
dc.date.available2010-01-15T00:02:26Z
dc.date.available2010-01-16T01:54:32Z
dc.date.created2007-08
dc.date.issued2009-05-15
dc.identifier.urihttp://hdl.handle.net/1969.1/ETD-TAMU-1549
dc.description.abstractParking 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.mediumelectronicen
dc.format.mimetypeapplication/pdf
dc.language.isoen_US
dc.subjectcombinatoricsen
dc.subjectparking functionsen
dc.subjectalgorithmsen
dc.titleGraph searching and a generalized parking functionen
dc.typeBooken
dc.typeThesisen
thesis.degree.departmentMathematicsen
thesis.degree.disciplineMathematicsen
thesis.degree.grantorTexas A&M Universityen
thesis.degree.nameDoctor of Philosophyen
thesis.degree.levelDoctoralen
dc.contributor.committeeMemberAguiar, Marcelo
dc.contributor.committeeMemberChen, Jianer
dc.contributor.committeeMemberRojas, Maurice
dc.contributor.committeeMemberSchenck, Henry
dc.contributor.committeeMemberTretkoff, Paula
dc.type.genreElectronic Dissertationen
dc.type.materialtexten
dc.format.digitalOriginborn digitalen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record