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

spanning treescharacteristic polynomialAztec diamondscheckerboard graphsgeneralized game of checkers

Mathematics Subject Classification ID

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

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.

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

• 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?)
• Alternating-sign matrices and domino tilings. I
• Complexite et circuits euleriens dans les sommes tensorielles de graphes
• Recent results in the theory of graph spectra
• The Kronecker Product of Graphs
• To the graph theory

Cited in

(7)

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

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)