| |
|
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 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
|
|