Aztec diamonds, checkerboard graphs, and spanning trees

DOI10.1023/A:1008605912200MaRDI QIDQ1361460zbMATH OpenOpenAlexFDO

Authors Donald E. Knuth

Publication date 25 November 1997

Published in Journal of Algebraic Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/9501234

zbMATH Keywords

Aztec diamondscharacteristic polynomialcheckerboard graphsgeneralized game of checkersspanning trees

Mathematics Subject Classification ID

Trees (05C05) Enumeration in graph theory (05C30) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

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.

Review text

The characteristic polynomial of a graph that represents nonjump moves is a generalized game of checkers (that is, the \(n\times m\) game of checkers). The number of spanning trees is also determined, in particular proving a conjecture of R. P. Stanley.

Recommendations

• Symmetry classes of spanning trees of aztec diamonds and perfect matchings of odd squares with a unit hole
• The energy and spanning trees of the Aztec diamonds
• A visual proof of a result of Knuth on spanning trees of Aztec diamonds in the case of odd order
• Parity party with picture proofs: an odd checkerboard problem
• scientific article; zbMATH DE number 3966096

Cites work

• Alternating-sign matrices and domino tilings. I
• Complexite et circuits euleriens dans les sommes tensorielles de graphes
• scientific article; zbMATH DE number 3717357 (Why is no real title available?)
• scientific article; zbMATH DE number 3775559 (Why is no real title available?)
• scientific article; zbMATH DE number 3623609 (Why is no real title available?)
• scientific article; zbMATH DE number 487720 (Why is no real title available?)
• scientific article; zbMATH DE number 3204642 (Why is no real title available?)
• Recent results in the theory of graph spectra
• The Kronecker Product of Graphs
• To the graph theory

Cited in

(8)

• A complementation theorem for perfect matchings of graphs having a cellular completion
• The number of spanning trees of plane graphs with reflective symmetry
• The Q-spectrum and spanning trees of tensor products of bipartite graphs
• The limit checker number of a graph
• The energy and spanning trees of the Aztec diamonds
• Modern theory of electrical networks: from the matrix-tree theorem to the theory of cluster varieties
• A visual proof of a result of Knuth on spanning trees of Aztec diamonds in the case of odd order
• Symmetry classes of spanning trees of aztec diamonds and perfect matchings of odd squares with a unit hole

This page was built for publication: Aztec diamonds, checkerboard graphs, and spanning trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1361460)