×

A spectral study of the Manhattan networks. (English) Zbl 1341.05151

Márquez, Alberto (ed.) et al., Proceedings of the 4th European conference on combinatorics, graph theory and applications, EuroComb’07, Seville, Spain, September 11–15, 2007. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 29, 267-271 (2007).
Summary: The multidimensional Manhattan networks are a family of digraphs with many appealing properties, such as vertex symmetry (in fact they are Cayley digraphs), easy routing, Hamiltonicity, and modular structure. From the known structural properties of these digraphs, we fully determine their spectra, which always contain the spectra of hypercubes. In particular, in the standard (two-dimensional) case it is shown that their line digraph structure imposes the presence of the zero eigenvalue with a large multiplicity.
For the entire collection see [Zbl 1137.05002].

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C82 Small world graphs, complex networks (graph-theoretic aspects)
05C20 Directed graphs (digraphs), tournaments
05C76 Graph operations (line graphs, products, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Balbuena, C.; Ferrero, D.; Marcote, X.; Pelayo, I., Algebraic properties of a digraph and its line digraph, J. Intercon. Networks, 4, 377-393 (2003)
[2] Biggs, N., Algebraic Graph Theory (1993), Cambridge University Press: Cambridge University Press Cambridge
[3] Comellas, F., C. Dalfó and M.A. Fiol, The multidimensional Manhattan networks; Comellas, F., C. Dalfó and M.A. Fiol, The multidimensional Manhattan networks
[4] Fiol, M. A.; Mitjana, M., The spectra of some families of digraphs, Linear Algebra Appl., 423, 1, 109-118 (2007) · Zbl 1113.05063
[5] Maxemchuk, N. F., Routing in the Manhattan Street Network, IEEE Trans. Commun., 35, 5, 503-512 (1987)
[6] Morillo, P.; Fiol, M. A.; Fàbrega, J., The diameter of directed graphs associated to plane tessellations, Ars Comb., 20A, 17-27 (1985) · Zbl 0599.05029
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.