Skip to Main Content

Proceedings of the American Mathematical Society

Published by the American Mathematical Society since 1950, Proceedings of the American Mathematical Society is devoted to shorter research articles in all areas of pure and applied mathematics.

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

The 2024 MCQ for Proceedings of the American Mathematical Society is 0.85.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

The $Q$-spectrum and spanning trees of tensor products of bipartite graphs
HTML articles powered by AMS MathViewer

by Timothy Y. Chow
Proc. Amer. Math. Soc. 125 (1997), 3155-3161
DOI: https://doi.org/10.1090/S0002-9939-97-04049-5
PDF | Request permission

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
  • M. Ciucu, Perfect matchings, spanning trees, plane partitions and statistical physics, Ph.D. thesis, University of Michigan, Ann Arbor, MI, 1996.
  • Dragoš M. Cvetković, Michael Doob, and Horst Sachs, Spectra of graphs, Pure and Applied Mathematics, vol. 87, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1980. Theory and application. MR 572262
  • D. M. Cvetković and I. Gutman, A new spectral method for determining the number of spanning trees, Publ. Inst. Math. (Beograd) (N.S.) 29(43) (1981), 49–52. MR 657093
  • Noam Elkies, Greg Kuperberg, Michael Larsen, and James Propp, Alternating-sign matrices and domino tilings. I, J. Algebraic Combin. 1 (1992), no. 2, 111–132. MR 1226347, DOI 10.1023/A:1022420103267
  • M. Farzan and D. A. Waller, Kronecker products and local joins of graphs, Canadian J. Math. 29 (1977), no. 2, 255–269. MR 429614, DOI 10.4153/CJM-1977-027-1
  • N. Hartsfield and J. S. Werth, Spanning trees of the complete bipartite graph, Topics in combinatorics and graph theory (Oberwolfach, 1990) Physica, Heidelberg, 1990, pp. 339–346. MR 1100053
  • Thomas W. Hungerford, Algebra, Holt, Rinehart and Winston, Inc., New York-Montreal, Que.-London, 1974. MR 0354211
  • D. Knuth, Aztec diamonds, checkerboard graphs, and spanning trees, preprint.
  • Germain Kreweras, ComplexitĂ© et circuits eulĂ©riens dans les sommes tensorielles de graphes, J. Combin. Theory Ser. B 24 (1978), no. 2, 202–212 (French, with English summary). MR 486144, DOI 10.1016/0095-8956(78)90021-7
  • I. Pak, personal communication.
  • Horst Sachs, On the number of spanning trees, Proceedings of the Fifth British Combinatorial Conference (Univ. Aberdeen, Aberdeen, 1975) Congressus Numerantium, No. XV, Utilitas Math., Winnipeg, Man., 1976, pp. 529–535. MR 0427131
  • B. Sagan, personal communication.
  • R. Stanley, Research problem 251: Spanning trees of Aztec diamonds, Discrete Math. 157 (1996), 383–385.
  • H. N. V. Temperley (ed.), Combinatorics, London Mathematical Society Lecture Note Series, vol. 52, Cambridge University Press, Cambridge-New York, 1981. MR 633646
Similar Articles
Bibliographic Information
  • Timothy Y. Chow
  • Email: tchow@umich.edu
  • 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
  • © Copyright 1997 American Mathematical Society
  • 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