Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



The $Q$-spectrum and spanning trees
of tensor products of bipartite graphs

Author: Timothy Y. Chow
Journal: Proc. Amer. Math. Soc. 125 (1997), 3155-3161
MSC (1991): Primary 05C50, 05C05, 05C30; Secondary 15A18, 15A69
MathSciNet review: 1415578
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Recently, Knuth and Ciucu independently proved the surprising fact, conjectured by Stanley, that one connected component of the tensor product of a path with itself (the so-called ``Aztec diamond graph'') has four times as many spanning trees as the other connected component, independent of the length of the path. We show here that much more is true: the connected components of the tensor product of any connected bipartite multigraphs all have essentially the same $Q$-spectrum. It follows at once that there is a simple formula relating their numbers of spanning trees.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (1991): 05C50, 05C05, 05C30, 15A18, 15A69

Retrieve articles in all journals with MSC (1991): 05C50, 05C05, 05C30, 15A18, 15A69

Additional Information

Timothy Y. Chow

Keywords: $Q$-spectrum, Laplacian, spanning tree enumeration, matrix-tree theorem, Aztec diamond, Pr\"{u}fer codes
Received by editor(s): May 16, 1996
Additional Notes: The author was supported in part by an NSF postdoctoral fellowship.
Communicated by: Jeffry N. Kahn
Article copyright: © Copyright 1997 American Mathematical Society