Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!usc!isi.edu!quark.isi.edu!pi
From: pi@quark.isi.edu (Jen-I Pi)
Newsgroups: comp.theory
Subject: Re: Counting Spanning Trees
Keywords: spanning tree on grid graph, graph spectra theory.
Message-ID: <16810@venera.isi.edu>
Date: 18 Feb 91 03:49:39 GMT
References: <1991Feb13.163500.20074@hoss.unl.edu>
Sender: news@isi.edu
Reply-To: pi@quark.isi.edu (Jen-I Pi)
Lines: 56

In article <1991Feb13.163500.20074@hoss.unl.edu>, memon@hoss.unl.edu (Nasir Memon) writes:
|> 
|> Hi,
|>     I have a few questions regarding enumeration/ranking etc. of
|>     spanning trees for a given graph. I would appreciate if you
|>     could send me any information and/or references. I am
|>     specifically interested in rectangular graphs (or grid
|>     graphs), i am not sure of the standard terminology used here,
|>     but the graphs look as follows
|> 
|>                  o-----o-----o-----o
|>                  |     |     |     |
|>                  o-----o-----o-----o
|>                  |     |     |     |
|>                  o-----o-----o-----o
|>                  |     |     |     |
|>                  o-----o-----o-----o
|> 
|>     The kind of questions i am looking for an answer to are as
|>     follows:
|> 
|>     Does there exist a nice formula for the number of labelled spanning
|>     trees of an MxN grid graph? How about the number of hamitonian
|>     paths?

There exist a formula for the graph that you are interested in by
the use of graph spectra techniques (c.f. [1] for detail).
In the case of mxn grid graph, the number of spanning tree is

\begin{displaymath}
4^{(m-1)(n-1)} \prod_{i=1}^{m-1} \prod_{j=1}^{n-1} \sin^{2} \frac{i\pi}{2m}
\frac{j\pi}{2n}
\end{displaymath}
(c.f. [2], p. 87).

I'll check for the hamitonian paths!

References:
[1] @book{cvetkovic80,
       author="D. M. Cvetkovi\'{c} and M. Doob and H. Sachs",
       title="Spectra of Graph-Theory and Application",
       publisher="Academic Press", year=1980, edition=2,}

[2] @book{cvetkovic88,
       author="D. M. Cvetkovi\'{c} and M. Doob and I. Gutman\
	 and A. Torga\v{s}ev",
       editor="P. L. Hammer",
       title="Recent Results in the Theory of Graph Spectra",
       publisher="North-Holland", year=1988, volume=36,
       series="Annals of Discrete Mathematics"}

Jen-I pi@vlsi-cad.isi.edu
MOSIS Project, USC/ISI
4676 Admiralty way
Marina del Rey, CA 90292-6695
(213)822-1511 x640