The Vertex Deletion Number and Splitting Number of a Triangulation of $C_n \times C_m$

The vertex deletion number $\phi(G)$ of a graph $G$ is the minimum number of vertices that must be deleted from $G$ to produce a planar graph. The splitting number $\sigma(G)$ of $G$ is the smallest number of vertex splitting operations that must be applied to $G$ to make it planar. Here we determine these topological invariants for the graph family ${\cal T}_{C_n \times C_m}$, a regular triangulation of the torus obtained by adding parallel diagonal edges to the faces of the rectangular toroidal grid $C_n \times C_m$. Specifically, we prove that the obvious upper bound $\phi = \sigma = \min\{n,m\}$ is also a lower bound.

1999