×

The spectra of Manhattan street networks. (English) Zbl 1144.05316

Summary: The multidimensional Manhattan street networks constitute a family of digraphs with many interesting 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 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.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C20 Directed graphs (digraphs), tournaments
05C38 Paths and cycles
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. Interconnection Networks, 4, 4, 377-393 (2003)
[2] Banerjee, S.; Jain, V.; Shah, S., Regular multihop logical topologies for lightwave networks, IEEE Comm. Surveys Tutorials, 2, First Quarter, 1 (1999)
[3] D. Banerjee, B. Mukherjee, S. Ramamurthy, The multidimensional torus: analysis of average hop distance and application as a multihop lightwave network, in: IEEE Int. Conf. on Comm., vol. 3, 1994, pp. 1675-1680.; D. Banerjee, B. Mukherjee, S. Ramamurthy, The multidimensional torus: analysis of average hop distance and application as a multihop lightwave network, in: IEEE Int. Conf. on Comm., vol. 3, 1994, pp. 1675-1680.
[4] Bang-Jensen, J.; Gutin, G., Digraphs: Theory, Algorithms and Applications, Springer Monographs in Mathematics (2003), Springer: Springer London
[5] N. Biggs, Algebraic Graph Theory, Cambridge University Press, Cambridge, 1974, second ed., 1993.; N. Biggs, Algebraic Graph Theory, Cambridge University Press, Cambridge, 1974, second ed., 1993. · Zbl 0284.05101
[6] W.L. Briggs, V.E. Henson, The DFT: An Owners’manual for the Discrete Fourier Transform, SIAM cop., Philadelphia, 1995.; W.L. Briggs, V.E. Henson, The DFT: An Owners’manual for the Discrete Fourier Transform, SIAM cop., Philadelphia, 1995.
[7] Chartrand, G.; Lesniak, L., Graphs & Digraphs (1996), Chapman and Hall: Chapman and Hall London · Zbl 0890.05001
[8] Chung, F. R.K., Diameters and eigenvalues, J. Amer. Math. Soc., 2, 2, 187-196 (1989) · Zbl 0678.05037
[9] F.R.K. Chung, The diameter and Laplacian eigenvalues of directed graphs, Electron. J. Comb. 13 (1) (2006) Note 4, 6 pp.; F.R.K. Chung, The diameter and Laplacian eigenvalues of directed graphs, Electron. J. Comb. 13 (1) (2006) Note 4, 6 pp. · Zbl 1084.05031
[10] Chung, F. R.K.; Faber, V.; Manteuffel, T. A., An upper bound on the diameter of a graph from eigenvalues associated with its Laplacian, SIAM J. Discrete Math., 7, 3, 443-457 (1994) · Zbl 0808.05072
[11] T.Y. Chung, D.P. Agrawal, On network characterization of and optimal broadcasting in the Manhattan Street Network, in: IEEE INFOCOM ’90, 1990, pp. 465-472.; T.Y. Chung, D.P. Agrawal, On network characterization of and optimal broadcasting in the Manhattan Street Network, in: IEEE INFOCOM ’90, 1990, pp. 465-472.
[12] Chung, T. Y.; Agrawal, D. P., Design and analysis of multidimensional Manhattan Street Networks, IEEE Trans. Comm., 41, 295-298 (1993) · Zbl 0775.94150
[13] Comellas, F.; Dalfó, C., Optimal broadcasting in 2-dimensional Manhattan street networks, Parallel Distrib. Comput. Networks, 246, 135-140 (2005)
[14] F. Comellas, C. Dalfó, M.A. Fiol, Multidimensional Manhattan street networks, SIAM J. Discrete Math., in press.; F. Comellas, C. Dalfó, M.A. Fiol, Multidimensional Manhattan street networks, SIAM J. Discrete Math., in press. · Zbl 1227.05156
[15] Comellas, F.; Fiol, M. A.; Gimbert, J.; Mitjana, M., Weakly distance-regular digraphs, J. Combin. Theory Ser. B, 90, 2, 233-255 (2004) · Zbl 1033.05100
[16] Coxeter, H. S.M.; Moder, W. O.J., Generators and Relations for Discrete Groups (1980), Springer Verlag: Springer Verlag Berlin · Zbl 0422.20001
[17] Fiol, M. A.; A Yebra, J. L.; Alegre, I., Line digraph iterations in the \((d,k)\) digraph problem, IEEE Trans. Comput., C-33, 5, 400-403 (1984) · Zbl 0528.68048
[18] Fiol, M. A.; Mitjana, M., The spectra of some families of digraphs, Linear Algebra Appl., 423, 1, 109-118 (2007) · Zbl 1113.05063
[19] Godsil, C. D., Algebraic Combinatorics (1993), Chapman and Hall: Chapman and Hall New York · Zbl 0814.05075
[20] Heuchenne, C., Sur une certaine correspondance entre graphes, Bull. Soc. Roy. Sci. Liège, 33, 12, 743-753 (1964) · Zbl 0134.43302
[21] Khasnabish, B., Topological properties of Manhattan Street Networks, Electronics Lett., 25, 20, 1388-1389 (1989)
[22] Maxemchuk, N. F., Routing in the Manhattan Street Network, IEEE Trans. Comm., 35, 5, 503-512 (1987)
[23] J.C. Montserrat, Propiedades Matriciales de los Grafos Dirigidos, Ms. Dissertation (in Spanish), Univ. Politècnica de Catalunya, Spain, 1986.; J.C. Montserrat, Propiedades Matriciales de los Grafos Dirigidos, Ms. Dissertation (in Spanish), Univ. Politècnica de Catalunya, Spain, 1986.
[24] Morillo, P.; Fiol, M. A.; Fàbrega, J., The diameter of directed graphs associated to plane tessellations, Ars Combin., 20A, 17-27 (1985) · Zbl 0599.05029
[25] P. Sarnak, Some Applications of Modular Forms, Cambridge Tracts in Mathematics 99, Cambridge University Press, Cambridge CB2 1RP, UK, 1990.; P. Sarnak, Some Applications of Modular Forms, Cambridge Tracts in Mathematics 99, Cambridge University Press, Cambridge CB2 1RP, UK, 1990. · Zbl 0721.11015
[26] Tanner, R. M., Explicit constructions of concentrators from generalized n-gons, SIAM J. Algebraic Discrete Methods, 5, 287-293 (1984) · Zbl 0554.05045
[27] Varvarigos, E. A., Optimal communication algorithms for Manhattan Street Networks, Discrete Appl. Math., 83, 303-326 (1998) · Zbl 0905.90071
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.