# On some special spanning trees of grid graphs

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:

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

• 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! – gmath Nov 3 '14 at 20:38
• Thanks. I have tried that and it seems that this indeed gives spanning trees with much less corridors. But still there remains some. – F. C. Jan 6 '15 at 17:17