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

HTML articles powered by AMS MathViewer

- by Timothy Y. Chow PDF
- Proc. Amer. Math. Soc.
**125**(1997), 3155-3161 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**

## Additional 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