×

The spectra of wrapped butterfly digraphs. (English) Zbl 1018.05066

Summary: The knowledge of the spectrum of a (di)graph is relevant for estimating some of its structural properties, which provide information on the topological and communication properties of the corresponding networks. Among these properties, we have, for instance, edge-expansion and node-expansion, bisection width, diameter, maximum cut, connectivity, and partitions. In this paper, we determine the complete spectra (eigenvalues and multiplicities) of wrapped butterfly digraphs.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C20 Directed graphs (digraphs), tournaments
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Barth, Inform Process Lett 51 pp 175– (1994)
[2] Bermond, Discr Appl Math 84 pp 21– (1998)
[3] Bermond, Parallel Process Lett 8 pp 371– (1998)
[4] and New spectral lower bounds on the bisection width of graphs, Proc WG’00, and (Editors), LNCS 1928, Springer, Berlin, 2000, pp. 23-34.
[5] Algebraic graph theory, Cambridge University Press, Cambridge, 1974; 2nd ed., 1993.
[6] and On the bisection width and expansion of butterfly networks, Proc First Merged Int Parallel Processing Symp and Symp on Parallel and Distributed Processing. March 30-April 3, Orlando, FL, 1998.
[7] and Combinatorial matrix theory, Cambridge University Press, Cambridge, 1991.
[8] Chung, J Am Math Soc 2 pp 187– (1989)
[9] Chung, SIAM J Discr Math 7 pp 443– (1994)
[10] and Routing on butterfly networks with random faults, Proc IEEE Annu Symp on Foundations of Computer Science, 1995, pp. 558-570. · Zbl 0938.68528
[11] and Weakly-distance regular digraphs (submitted).
[12] Comellas, Parallel Process Lett 8 pp 549– (1998)
[13] and Towards optimal load balancing topologies, Proc 6th EuroPar Conf, and (Editors), LNCS 1900, Springer, Berlin, 2000, pp. 277-287.
[14] Diekmann, Parallel Comput 25 pp 789– (1999)
[15] and Scalable sparse topologies with small spectrum, Proc 18th Annual Symp on Theoretical Aspects of Computer Science (STACS), and (Editors), LNCS 2010, Springer, Berlin, 2001, pp. 218-229. · Zbl 0976.68114
[16] Feldmann, Parallel Process Lett 2 pp 13– (1992)
[17] Hagen, IEEE Dig Techn Pap pp 10– (1991)
[18] Hagen, IEEE Trans CAD/ICS 11 pp 1074– (1992)
[19] Hoffman, Proc Am Math Soc 16 pp 303– (1965)
[20] Hwang, Networks 35 pp 161– (2000)
[21] Klasing, Discr Appl Math 53 pp 183– (1994)
[22] Maggs, SIAM J Comput 28 pp 984– (1999)
[23] Maggs, Algorithmica 28 pp 438– (2000)
[24] Mohar, J Combin Theory Ser B 47 pp 274– (1989)
[25] ?The Laplacian spectrum of graphs,? Graph theory, combinatorics, and applications, and (Editors), Wiley, New York, 1991, Vol. 2, pp. 871-898. · Zbl 0840.05059
[26] Wong, Networks 26 pp 145– (1995)
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.