Partitioned Tensor Products and Their Spectra
Donald E. Knuth
DOI: 10.1023/A:1008662029947
Abstract
A pleasant family of graphs defined by Godsil and McKay is shown to have easily computed eigenvalues in many cases.
Pages: 259–267
Keywords: partitioned tensor product; graph spectra; generalized products of graphs; Cayley graph; compatible partition
Full Text: PDF
References
1. Drago\check s M. Cvetković, Michael Doob, and Horst Sachs, Spectra of Graphs, Academic Press, New York, 1980.
2. G. Frobenius, “ \ddot Uber vertauschbare Matrizen,” Sitzungsberichte der K\ddot oniglich Preußischen Akademie der Wissenschaften zu Berlin, 1896, pp. 601-614. Reprinted in his Gesammelte Abhandlungen, Springer, Berlin, 1968, Vol. 2, pp. 705-718. P1: KCU/SNG P2: MVG/ASH QC: RPS Journal of Algebraic Combinatorics KL434-05-Knuth-II April 23, 1997 10:0 PARTITIONED TENSOR PRODUCTS AND THEIR SPECTRA 267
3. C. Godsil and B. McKay, “Products of graphs and their spectra,” in Combinatorial Mathematics IV, A. Dold and B. Eckmann (Eds.), Lecture Notes in Mathematics, Vol. 560, pp. 61-72, 1975.
4. C. Godsil and B. McKay, “Some computational results on the spectra of graphs,” in Combinatorial Mathematics IV, A. Dold and B. Eckmann (Eds.), Lecture Notes in Mathematics, Vol. 560, pp. 73-82, 1975.
5. C.D. Godsil and B.D. McKay, “Constructing cospectral graphs,” Æquationes Mathematicæ 25 (1982), 257- 268.
6. Gene H. Golub and Charles F. Van Loan, Matrix Computations, Johns Hopkins University Press, Baltimore, 1983.
7. Marvin Marcus and Henrik Minc, A Survey of Matrix Theory and Matrix Inequalities, Allyn and Bacon, Boston, 1964.
2. G. Frobenius, “ \ddot Uber vertauschbare Matrizen,” Sitzungsberichte der K\ddot oniglich Preußischen Akademie der Wissenschaften zu Berlin, 1896, pp. 601-614. Reprinted in his Gesammelte Abhandlungen, Springer, Berlin, 1968, Vol. 2, pp. 705-718. P1: KCU/SNG P2: MVG/ASH QC: RPS Journal of Algebraic Combinatorics KL434-05-Knuth-II April 23, 1997 10:0 PARTITIONED TENSOR PRODUCTS AND THEIR SPECTRA 267
3. C. Godsil and B. McKay, “Products of graphs and their spectra,” in Combinatorial Mathematics IV, A. Dold and B. Eckmann (Eds.), Lecture Notes in Mathematics, Vol. 560, pp. 61-72, 1975.
4. C. Godsil and B. McKay, “Some computational results on the spectra of graphs,” in Combinatorial Mathematics IV, A. Dold and B. Eckmann (Eds.), Lecture Notes in Mathematics, Vol. 560, pp. 73-82, 1975.
5. C.D. Godsil and B.D. McKay, “Constructing cospectral graphs,” Æquationes Mathematicæ 25 (1982), 257- 268.
6. Gene H. Golub and Charles F. Van Loan, Matrix Computations, Johns Hopkins University Press, Baltimore, 1983.
7. Marvin Marcus and Henrik Minc, A Survey of Matrix Theory and Matrix Inequalities, Allyn and Bacon, Boston, 1964.