Aztec Diamonds, Checkerboard Graphs, and Spanning Trees
Donald E. Knuth
DOI: 10.1023/A:1008605912200
Abstract
This note derives the characteristic polynomial of a graph that represents nonjump moves in a generalized game of checkers. The number of spanning trees is also determined.
Pages: 253–257
Keywords: aztec diamond; spanning tree; graph spectra; enumeration
Full Text: PDF
References
1. C.W. Borchardt, “Ueber eine der Interpolation entsprechende Darstellung der Eliminations-Resultante,” Journal f\ddot ur die reine und angewandte Mathematik 57 (1860), 111-121.
2. Karel \check Culik, “Zur theorie der graphen,” \check Casopis pro P\check estování Matematiky 83 (1958), 133-155.
3. Drago\check s M. Cvetković, Michael Doob, and Horst Sachs, Spectra of Graphs, Academic Press, New York, 1980.
4. D. Cvetković and I. Gutman, “A new spectral method for determining the number of spanning trees,” Publications de l'Institut Mathématique, Beograd, 29(43) (1981), 49-52.
5. Drago\check s M. Cvetković, Michael Doob, Ivan Gutman, and Aleksandar Torga\check sev, “Recent Results in the Theory of Graph Spectra,” Annals of Discrete Mathematics 36 (1988).
6. Noam Elkies, Greg Kuperberg, Michael Larsen, and James Propp, “Alternating-sign matrices and domino tilings,” J. Alg. Combin. 1 (1992), 111-132 and 219-234.
7. 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 560 (1975), 61-72.
8. Germain Kreweras, “Complexité et circuits eulériens dans les sommes tensorielles de graphes,” Journal of Combinatorial Theory B24 (1978), 202-212.
9. László Lovász, Combinatorial Problems and Exercises, 2nd Edition, Budapest, Akadémiai Kiadó, 1993.
10. Marvin Marcus and Henrik Minc, A Survey of Matrix Theory and Matrix Inequalities, Boston, Allyn and Bacon, 1964.
11. Richard P. Stanley, “Spanning trees of Aztec diamonds,” open problem presented at a DIMACS meeting on Formal Power Series and Algebraic Combinatorics, Piscataway, NJ, May 23-27, 1994.
12. Paul M. Weichsel, “The Kronecker product of graphs,” Proceedings of the American Mathematical Society 13 (1962), 47-52.
2. Karel \check Culik, “Zur theorie der graphen,” \check Casopis pro P\check estování Matematiky 83 (1958), 133-155.
3. Drago\check s M. Cvetković, Michael Doob, and Horst Sachs, Spectra of Graphs, Academic Press, New York, 1980.
4. D. Cvetković and I. Gutman, “A new spectral method for determining the number of spanning trees,” Publications de l'Institut Mathématique, Beograd, 29(43) (1981), 49-52.
5. Drago\check s M. Cvetković, Michael Doob, Ivan Gutman, and Aleksandar Torga\check sev, “Recent Results in the Theory of Graph Spectra,” Annals of Discrete Mathematics 36 (1988).
6. Noam Elkies, Greg Kuperberg, Michael Larsen, and James Propp, “Alternating-sign matrices and domino tilings,” J. Alg. Combin. 1 (1992), 111-132 and 219-234.
7. 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 560 (1975), 61-72.
8. Germain Kreweras, “Complexité et circuits eulériens dans les sommes tensorielles de graphes,” Journal of Combinatorial Theory B24 (1978), 202-212.
9. László Lovász, Combinatorial Problems and Exercises, 2nd Edition, Budapest, Akadémiai Kiadó, 1993.
10. Marvin Marcus and Henrik Minc, A Survey of Matrix Theory and Matrix Inequalities, Boston, Allyn and Bacon, 1964.
11. Richard P. Stanley, “Spanning trees of Aztec diamonds,” open problem presented at a DIMACS meeting on Formal Power Series and Algebraic Combinatorics, Piscataway, NJ, May 23-27, 1994.
12. Paul M. Weichsel, “The Kronecker product of graphs,” Proceedings of the American Mathematical Society 13 (1962), 47-52.