The splitting number of complete bipartite graphs (Q793047)

A new and interesting topological invariant of graphs, called splitting number, is introduced to measure, in a way, the ''closeness to embeddability on a surface''. The splitting number \(sp_ S(G)\) of a graph G (with respect to a closed surface S) is defined as the smallest number of vertex splittings (i.e., replacing a vertex v by two non-adjacent vertices \(v_ 1\), \(v_ 2\) in such a way that every vertex formerly adjacent to v is joined to at least one of \(v_ 1\), \(v_ 2)\) needed to transform G into a graph embeddable on S. It is proved that for any surface S (orientable or not) of Euler characteristic E(S), \[ sp_ S(K_{m,n})=\max(\lceil(m-2)(n-2)/2\rceil -2+E(S),0). \] This yields a new way of obtaining the well known orientable and non-orientable genus formulas for complete bipartite graphs.