memon@hoss.unl.edu (Nasir Memon) (02/14/91)
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?
Are ranking/unranking functions known for labelled spanning
trees of these graphs?
Any pointers, comments, suggestions, references etc will be
highly appreciated.
thanks
nasirpi@quark.isi.edu (Jen-I Pi) (02/18/91)
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