Skewness, splitting number and vertex deletion of some toroidal meshes

dc.creatorMENDONCA NETO, C. F. X. de
dc.creatorCONSTANTINO, A. A.
dc.creatorXAVIER, E. F.
dc.creatorSTOLFI, J.
dc.creatorFARIA, L.
dc.creatorFIGUEIREDO, C. M. H. de
dc.date2009
dc.date2013-07-26T17:57:38Z
dc.date2016-06-30T18:12:38Z
dc.date2013-07-26T17:57:38Z
dc.date2016-06-30T18:12:38Z
dc.date.accessioned2018-03-29T01:52:57Z
dc.date.available2018-03-29T01:52:57Z
dc.identifierARS COMBINATORIA, v.92, p.53-65, 2009
dc.identifier0381-7032
dc.identifierhttp://apps.isiknowledge.com/InboundService.do?Func=Frame&product=WOS&action=retrieve&SrcApp=EndNote&UT=000267240700005&Init=Yes&SrcAuth=ResearchSoft&mode=FullRecord
dc.identifierhttp://apps.isiknowledge.com/InboundService.do?Func=Frame&product=WOS&action=retrieve&SrcApp=EndNote&UT=000267240700005&Init=Yes&SrcAuth=ResearchSoft&mode=FullRecord
dc.identifierhttp://www.repositorio.unicamp.br/jspui/handle/REPOSIP/354
dc.identifierhttp://repositorio.unicamp.br/jspui/handle/REPOSIP/354
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/1308282
dc.descriptionThe skewness sk(G) of a graph G = (V, E) is the smallest integer sk(G) >= 0 such that a planar graph can be obtained from G by the removal of sk(C) edges. The splitting number sp(G) of C is the smallest integer sp(G) >= 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) >= 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) x 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 Tc(m) x c(n) of C(m) x C(n) in the torus, and an hexagonal mesh Hc(m) x c(n), the dual of Tc(m) x c(n) in the torus. It is established that sp(Tc(m) x c(n)) = vd(Tc(m) x c(n) = sk(Hc(m) x c(n)) = sp(Hc(m) x c(n)) = vd(Hc(m) x c(n)) = min{m, n} and that sk(Tc(m) x c(n)) = 2 min {m, n}.
dc.description92
dc.description53
dc.description65
dc.languageeng
dc.publisherCHARLES BABBAGE RES CTR
dc.publisherCanadá
dc.relationArs Combinatoria
dc.rightsfechado
dc.rightsCopyright CHARLES BABBAGE RES CTR
dc.sourceWOS
dc.subjecttopological graph theory
dc.subjectgraph drawing
dc.subjecttoroidal mesh
dc.subjectplanarity
dc.subjectC-N
dc.subjectMathematics
dc.titleSkewness, splitting number and vertex deletion of some toroidal meshes
dc.typeArtículos de revistas
dc.typeArtículos de revistas
dc.typeArtículos de revistas


Este ítem pertenece a la siguiente institución