Aztec diamonds, checkerboard graphs, and spanning trees

DOI10.1023/A:1008605912200zbMATH Open0876.05067arXivmath/9501234OpenAlexW1807017871MaRDI QIDQ1361460FDOQ1361460

Authors: Donald E. Knuth 

Publication date: 25 November 1997

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Alternating-sign matrices and domino tilings. I
• Title not available (Why is that?)
• Recent results in the theory of graph spectra
• The Kronecker Product of Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• To the graph theory
• Complexite et circuits euleriens dans les sommes tensorielles de graphes

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)