Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!uakari.primate.wisc.edu!umriscc!maverick.ksu.ksu.edu!hoss!hoss.unl.edu!memon
From: memon@hoss.unl.edu (Nasir Memon)
Newsgroups: comp.theory
Subject: Counting Spanning Trees
Message-ID: <1991Feb13.163500.20074@hoss.unl.edu>
Date: 13 Feb 91 16:35:00 GMT
Sender: news@hoss.unl.edu (Network News Administer)
Organization: University of Nebraska - Lincoln
Lines: 32


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
    nasir