Skewness, Splitting Number and Vertex Deletion of Some Toroidal Meshes

C.F.X.de Mendonca Neto1, A.A. Constantino2, E.F. Xavier3, J. Stolfi3, L. Faria4, C.M.H.de Figueiredo5
1Escola de Artes, Ciéncias e Humanidades, USP, Sao Paulo, SP, Brazil
2Depto. de Informatica, UEM, Maringd, PR, Brazil
3Instituto de Computacéo, Unicamp, Campinas, SP, Brazil
4Faculdade de Formagao de Professores, UERJ, Sao Goncalo, RJ, Brazil
5UInstituto de Matemdtica, UFRJ, and COPPE Sistemas e Computagao, UFRJ , Rio de Janeiro, RJ, Brazil

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\}\).