I would like to know if there are existing results on the following objects:

spanning trees of a grid graph, with no corridor

where a corridor is a vertex having exactly two neighbors, on opposite sides.

Here is a picture of a spanning tree with corridors in red:

spanning tree with corridors in red

I would be interested in counting and random generation. Is there some variant of the classical methods for spanning trees that would work for them?

I am motivated by some representation-theoretic setting where a corridor allows to factorise the situation.

The similar problem for planar binary trees is much simpler (see Oeis sequence A5554).

  • 1
    $\begingroup$ Wired spanning trees can be generated by Wilson's algorithm via loop erased random walk. In your situation, my guess would be generating via a loop erased walk where we alternately take (random )steps in $X$ and $Y$ co-ordinate? It needs to be checked though! $\endgroup$
    – gmath
    Nov 3 '14 at 20:38
  • $\begingroup$ Thanks. I have tried that and it seems that this indeed gives spanning trees with much less corridors. But still there remains some. $\endgroup$
    – F. C.
    Jan 6 '15 at 17:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.