Show simple item record

dc.contributor.authorComellas, Francesc
dc.contributor.authorDalfó, Cristina
dc.contributor.authorFiol, Miguel Angel
dc.description.abstractWe study the main properties of a new product of bipartite digraphs which we call Manhattan product. This product allows us to understand the subjacent product in the Manhattan street networks and can be used to built other networks with similar good properties. It is shown that if all the factors of such a product are (directed) cycles, then the digraph obtained is a Manhattan street network, a widely studied topology for modeling some interconnection networks. To this respect, it is proved that many properties of these networks, such as high symmetries, reduced diameter and the presence of Hamiltonian cycles, are shared by the Manhattan product of some digraphs. Moreover, we show that the Manhattan product of two Manhattan streets networks is also a Manhattan street network. Finally, some sufficient conditions for the Manhattan product of two Cayley digraphs to be also a Cayley digraph are given. Throughout our study we use some interesting recent concepts, such as the unilateral distance and related graph invariants.ca_ES
dc.description.sponsorshipThis research was supported by the Ministry of Science and Innovation (Spain) and the European Regional Development Fund under project MTM2011-28800-C02-01-1 and by the Catalan Research Council under project 2009SGR1387.ca_ES
dc.publisherIndonesian Combinatorial Society (InaCombS); Graph Theory and Applications (GTA) Research Centre; University of Newcastle, Australia; Institut Teknologi Bandung (ITB), Indonesiaca_ES
dc.relation.isformatofReproducció del document publicat a
dc.relation.ispartofElectronic Journal of Graph Theory and Applications, 2013, vol. 1, núm. 1, p. 11–27ca_ES
dc.rightscc-by-sa (c) F. Comellas et al., 2013ca_ES
dc.subjectSelf-converse digraphca_ES
dc.subjectManhattan street networkca_ES
dc.subjectUnilateral diameterca_ES
dc.subjectCayley digraphca_ES
dc.titleThe Manhattan Product of Digraphsca_ES

Files in this item


This item appears in the following Collection(s)

Show simple item record

cc-by-sa (c) F. Comellas et al., 2013
Except where otherwise noted, this item's license is described as cc-by-sa (c) F. Comellas et al., 2013