Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Proceedings of the American Mathematical Society
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
Email: tchow@umich.edu

DOI: http://dx.doi.org/10.1090/S0002-9939-97-04049-5
PII: S 0002-9939(97)04049-5
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