|
The  -spectrum and spanning trees of tensor products of bipartite graphs
Author(s):
Timothy
Y.
Chow
Journal:
Proc. Amer. Math. Soc.
125
(1997),
3155-3161.
MSC (1991):
Primary 05C50, 05C05, 05C30;
Secondary 15A18, 15A69
Retrieve article in:
PDF
This article is available free of charge
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.
References:
- 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
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
Affiliation:
Department of Mathematics, University of Michigan, Ann Arbor, Michigan 48109
Email:
tchow@umich.edu
DOI:
10.1090/S0002-9939-97-04049-5
PII:
S 0002-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
Copyright of article:
Copyright
1997,
American Mathematical Society
|
Comments: webmaster@ams.org