Genus distribution of graphs under surgery: adding edges and splitting vertices (Q983423)

Let \(g_k(G)\) give the number of labeled 2-cell imbeddings of the connected graph \(G\) (which can have either loops or multiple edges) into the orientable surface \(S_k\). The sequence \(gd(G)= \{G_k\}\), as \(k\) ranges over the nonnegative integers, is called the genus distribution of \(G\). The author studies the derivation of genus distributions for graphs obtained by surgical operations on graphs with known genus distribution, focusing on the operation of adding an edge, and also the operation of splitting a vertex (the inverse of the latter operation is edge contraction). The main result is a splitting theorem: Let \(w\) be a vertex of degree 4 in a graph \(G\), with \(H_1\), \(H_2\), and \(H_3\) the three graphs into which \(G\) can be split at \(w\) so that the two new vertices of each split have degree 3. Then \(2gd(G)= gd(H_1)+ gd(H_2)+ gd(H_3)\). For example, the wheel graph \(W_4\) splits at its central vertex into either \(K_2\times C_3\) (two ways) or \(K_{3,3}\) (one way). It is known that \(gd(K_2\times C_3)= \{2,38,24\}\) and that \(gd(K_{3,3})=\{0,40,24\}\); thus \(gd(W_4)= (1/2)(2\{2,38,24\}+ \{0, 40,24\})\{2,58,36\}\).