The Splitting Number and Skewness of \(C_n \times C_m\)

Abstract

The skewness of a graph \(G\) is the minimum number of edges that need to be deleted from \(G\) to produce a planar graph. The splitting number of a graph \(G\) is the minimum number of splitting steps needed to turn \(G\) into a planar graph; where each step replaces some of the edges \(\{u,v\}\) incident to a selected vertex \(u\) by edges \(\{u’,v\}\), where \(u’\) is a new vertex. We show that the splitting number of the toroidal grid graph \(C_n \times C_m\) is \(\min\{n,m\} – 2\delta_{n,3}\delta_{m,3} – \delta_{n,4}\delta_{m,3} – \delta_{n,3}\delta_{m,4}\) and its skewness is \(\min\{n, m\} – \delta_{n,3}\delta_{m,3 }- \delta_{n,4}\delta_{m,3} – \delta_{n,3}\delta_{m,4}\). Here, \(\delta\) is the Kronecker symbol, i.e., \(\delta_{i,j}\) is \(1\) if \(i = j\), and \(0\) if \(i \neq j\).