 

Jonathan L. Gross
Genus distribution of graphs under surgery: adding edges and splitting vertices view print


Published: 
May 31, 2010 
Keywords: 
Graph, genus distribution, contracting and splitting 
Subject: 
05C15 


Abstract
Our concern is deriving genus distributions of graphs obtained by surgical operations on graphs whose genus distribution is known. One operation in focus here is adding an edge. The other is splitting a vertex, for which the inverse operation is edgecontraction. Our main result is this Splitting Theorem: Let G be a graph and w a 4valent vertex of G. Let H_{1}, H_{2}, and H_{3} be the three graphs into which G can be split at w, so that the two new vertices of each split are 3valent. Then 2gd(G) = gd(H_{1}) + gd(H_{2}) + gd(H_{3}).


Author information
Department of Computer Science, Columbia University, New York, NY 10027

