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

DOI:
https://doi.org/10.1090/S0002-9939-97-04049-5

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 -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.**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**

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:
https://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