14
$\begingroup$

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).

$\endgroup$
2
  • 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.