The Manhattan Product of Digraphs
MetadataShow full item record
We 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.
Is part ofElectronic Journal of Graph Theory and Applications, 2013, vol. 1, núm. 1, p. 11–27
European research projects
The following license files are associated with this item:
Except where otherwise noted, this item's license is described as cc-by-sa (c) F. Comellas et al., 2013
Showing items related by title, author, creator and subject.
Dalfó, Cristina; Fiol, Miguel Angel (Indonesian Combinatorial Society (InaCombS); Graph Theory and Applications (GTA) Research Centre; University of Newcastle, Australia; Institut Teknologi Bandung (ITB), Indonesia, 2014)We study the (Delta,D) and (Delta,N) problems for double-step digraphs considering the unilateral distance, which is the minimum between the distance in the digraph and the distance in its converse digraph, obtained by ...
Dalfó, Cristina; Fiol, Miguel Angel; López Lorenzo, Ignacio (Elsevier B.V., 2018)A mixed graph G can contain both (undirected) edges and arcs (directed edges). Here we derive an improved Moore-like bound for the maximum number of vertices of a mixed graph with diameter at least three. Moreover, a ...
Dalfó, Cristina; Fiol, Miguel Angel (World Scientific Publishing, 2019)It is known that many networks modeling real-life complex systems are small-word (large local clustering and small diameter) and scale-free (power law of the degree distribution), and very often they are also hierarchical. ...