Remote Access Proceedings of the American Mathematical Society
Green Open Access

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
DOI: https://doi.org/10.1090/S0002-9939-97-04049-5
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

Keywords: $Q$-spectrum, Laplacian, spanning tree enumeration, matrix-tree theorem, Aztec diamond, PrĂĽ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