New York Journal of Mathematics
Volume 16 (2010) 161-178


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

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 edge-contraction. Our main result is this Splitting Theorem: Let G be a graph and w a 4-valent vertex of G. Let H1, H2, and H3 be the three graphs into which G can be split at w, so that the two new vertices of each split are 3-valent. Then 2gd(G) = gd(H1) + gd(H2) + gd(H3).

Author information

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