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
MathSciNet review: 1415578
Full-text PDF

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?)

  • 1. M. Ciucu, Perfect matchings, spanning trees, plane partitions and statistical physics, Ph.D. thesis, University of Michigan, Ann Arbor, MI, 1996.
  • 2. D. Cvetkovi\'{c}, M. Doob, and H. Sachs, Spectra of Graphs: Theory and Application, Academic Press, New York, NY, 1980. MR 81i:05054
  • 3. D. Cvetkovi\'{c} and I. Gutman, A new spectral method for determining the number of spanning trees, Publ. Inst. Math. (Beograd) 29 (1981), 49-52. MR 83f:05046
  • 4. N. Elkies, G. Kuperberg, M. Larsen, and J. Propp, Alternating-sign matrices and domino tilings, J. Algebraic Combin. 1 (1992), 111-132 and 219-234. MR 94f:52035; MR 94f:52036
  • 5. M. Farzan and D. A. Waller, Kronecker products and local joins of graphs, Can. J. Math. 29 (1977), 255-269. MR 55:2625
  • 6. N. Hartsfield and J. S. Werth, Spanning trees of the complete bipartite graph, Topics in Combinatorics and Graph Theory (R. Bodendiek and R. Henn, eds.), Physica-Verlag, Heidelberg, 1990. MR 91m:05100
  • 7. T. Hungerford, Algebra, Holt, Rinehart and Winston, Inc., New York, NY, 1974. MR 50:6693
  • 8. D. Knuth, Aztec diamonds, checkerboard graphs, and spanning trees, preprint.
  • 9. G. Kreweras, Complexité et circuits eulériens dans les sommes tensorielles de graphes, J. Combin. Theory B24 (1978), 202-212. MR 80c:05099
  • 10. I. Pak, personal communication.
  • 11. H. Sachs, On the number of spanning trees, Proc. 5th Brit. Combin. Conf., Aberdeen 1975 (C. St. J. A. Nash-Williams and J. Sheehan, eds.), Winnipeg, 1976, pp. 529-535. MR 55:167
  • 12. B. Sagan, personal communication.
  • 13. R. Stanley, Research problem 251: Spanning trees of Aztec diamonds, Discrete Math. 157 (1996), 383-385.
  • 14. H. N. V. Temperley, Combinatorics, London Math. Soc. Lecture Notes Series, vol. 13, 1974, pp. 202-204. MR 82i:05001

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