The -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 -spectrum. It follows at once that there is a simple formula relating their numbers of spanning trees.

**1.**M. Ciucu,*Perfect matchings, spanning trees, plane partitions and statistical physics*, Ph.D. thesis, University of Michigan, Ann Arbor, MI, 1996.**2.**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****3.**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****4.**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**, 10.1023/A:1022420103267

Noam Elkies, Greg Kuperberg, Michael Larsen, and James Propp,*Alternating-sign matrices and domino tilings. II*, J. Algebraic Combin.**1**(1992), no. 3, 219–234. MR**1194076**, 10.1023/A:1022483817303**5.**M. Farzan and D. A. Waller,*Kronecker products and local joins of graphs*, Canad. J. Math.**29**(1977), no. 2, 255–269. MR**0429614****6.**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****7.**Thomas W. Hungerford,*Algebra*, Holt, Rinehart and Winston, Inc., New York-Montreal, Que.-London, 1974. MR**0354211****8.**D. Knuth,*Aztec diamonds, checkerboard graphs, and spanning trees*, preprint.**9.**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**, 10.1016/0095-8956(78)90021-7**10.**I. Pak, personal communication.**11.**Horst Sachs,*On the number of spanning trees*, Proceedings of the Fifth British Combinatorial Conference (Univ. Aberdeen, Aberdeen, 1975) Utilitas Math., Winnipeg, Man., 1976, pp. 529–535. Congressus Numerantium, No. XV. MR**0427131****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 (ed.),*Combinatorics*, London Mathematical Society Lecture Note Series, vol. 52, Cambridge University Press, Cambridge-New York, 1981. MR**633646**

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

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