The spectrum and spanning trees of tensor products of bipartite graphs
Author:
Timothy Y. Chow
Journal:
Proc. Amer. Math. Soc. 125 (1997), 31553161
MSC (1991):
Primary 05C50, 05C05, 05C30; Secondary 15A18, 15A69
MathSciNet review:
1415578
Fulltext 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 socalled ``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 YorkLondon, 1980. Theory and application. MR 572262
(81i:05054)
 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
(83f:05046)
 4.
Noam
Elkies, Greg
Kuperberg, Michael
Larsen, and James
Propp, Alternatingsign matrices and domino tilings. I, J.
Algebraic Combin. 1 (1992), no. 2, 111–132. MR 1226347
(94f:52035), http://dx.doi.org/10.1023/A:1022420103267
Noam
Elkies, Greg
Kuperberg, Michael
Larsen, and James
Propp, Alternatingsign matrices and domino tilings. II, J.
Algebraic Combin. 1 (1992), no. 3, 219–234. MR 1194076
(94f:52036), http://dx.doi.org/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
(55 #2625)
 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
(91m:05100)
 7.
Thomas
W. Hungerford, Algebra, Holt, Rinehart and Winston, Inc., New
YorkMontreal, Que.London, 1974. MR 0354211
(50 #6693)
 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 (80c:05099), http://dx.doi.org/10.1016/00958956(78)900217
 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
(55 #167)
 12.
B. Sagan, personal communication.
 13.
R. Stanley, Research problem 251: Spanning trees of Aztec diamonds, Discrete Math. 157 (1996), 383385.
 14.
H.
N. V. Temperley (ed.), Combinatorics, London Mathematical
Society Lecture Note Series, vol. 52, Cambridge University Press,
CambridgeNew York, 1981. MR 633646
(82i:05001)
 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), 4952. MR 83f:05046
 4.
 N. Elkies, G. Kuperberg, M. Larsen, and J. Propp, Alternatingsign matrices and domino tilings, J. Algebraic Combin. 1 (1992), 111132 and 219234. 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), 255269. 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.), PhysicaVerlag, 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), 202212. 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. NashWilliams and J. Sheehan, eds.), Winnipeg, 1976, pp. 529535. MR 55:167
 12.
 B. Sagan, personal communication.
 13.
 R. Stanley, Research problem 251: Spanning trees of Aztec diamonds, Discrete Math. 157 (1996), 383385.
 14.
 H. N. V. Temperley, Combinatorics, London Math. Soc. Lecture Notes Series, vol. 13, 1974, pp. 202204. 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
Email:
tchow@umich.edu
DOI:
http://dx.doi.org/10.1090/S0002993997040495
PII:
S 00029939(97)040495
Keywords:
$Q$spectrum,
Laplacian,
spanning tree enumeration,
matrixtree 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
