Methods for Computing Genus Distribution Using DoubleRooted Graphs
 Title:
 Methods for Computing Genus Distribution Using DoubleRooted Graphs
 Author(s):
 Khan, Imran Farid
 Thesis Advisor(s):
 Gross, Jonathan L.
 Date:
 2012
 Type:
 Dissertations
 Department(s):
 Computer Science
 Persistent URL:
 http://hdl.handle.net/10022/AC:P:12962
 Notes:
 Ph.D., Columbia University.
 Abstract:
 This thesis develops general methods for computing the genus distribution of various types of graph families, using the concept of doublerooted graphs, which are defined to be graphs with two vertices designated as roots (the methods developed in this dissertation are limited to the cases where one of the two roots is restricted to be of valence two). I define partials and productions, and I use these as follows: (i) to compute the genus distribution of a graph obtained through the vertex amalgamation of a doublerooted graph with a singlerooted graph, and to show how these can be used to obtain recurrences for the genus distribution of iteratively growing infinite graph families. (ii) to compute the genus distribution of a graph obtained (a) through the operation of selfvertexamalgamation on a doublerooted graph, and (b) through the operation of edgeaddition on a doublerooted graph, and finally (iii) to develop a method to compute the recurrences for the genus distribution of the graph family generated by the Cartesian product of P3 and Pn.
 Subject(s):
 Computer science
Mathematics
 Item views
 201
 Metadata:

text  xml
 Suggested Citation:
 Imran Farid Khan, 2012, Methods for Computing Genus Distribution Using DoubleRooted Graphs, Columbia University Academic Commons, http://hdl.handle.net/10022/AC:P:12962.