Skewness, Splitting Number and Vertex Deletion of Some Toroidal Meshes

Abstract

The skewness \(sk(G)\) of a graph \(G = (V, E)\) is the smallest integer \(sk(G) \geq 0\) such that a planar graph can be obtained from \(G\) by the removal of \(sk(G)\) edges. The splitting number \(sp(G)\) of \(G\) is the smallest integer \(sp(G) \geq 0\) such that a planar graph can be obtained from \(G\) by \(sp(G)\) vertex splitting operations. The vertex deletion \(vd(G)\) of \(G\) is the smallest integer \(vd(G) \geq 0\) such that a planar graph can be obtained from \(G\) by the removal of \(vd(G)\) vertices. Regular toroidal meshes are popular topologies for the connection networks of SIMD parallel machines. The best known of these meshes is the rectangular toroidal mesh \(C_m \times C_n\), for which is known the skewness, the splitting number and the vertex deletion. In this work we consider two related families: a triangulation \(T_{m,n}\) of \(C_m \times C_n\) in the torus, and an hexagonal mesh \(H_{m,n}\), the dual of \(\mathcal{T}_{C_m\times C_n}\) in the torus. It is established that \(sp(T_{m,n}) = vd(T_{m,n}) = sk(H_{C_m\times C_n}) = sp(\mathcal{H}_{C_m\times C_n}) = vd(\mathcal{H}_{m,n}) = \min\{m,n\}\) and that \(sk(\mathcal{T}_{C_m\times C_n}) = 2\min\{m, n\}\).