ITERATING THE BRANCHING OPERATION ON A DIRECTED GRAPH

The branching operation D, defined by Propp, assigns to any directed g raph G another directed graph D(G) whose vertices are the oriented roo ted spanning trees of the original graph G. We characterize the direct ed graphs G for which the sequence delta(G) = (G, D(G), D-2(G),...) co nverges, meaning that it is eventually constant. As a corollary of the proof we get the following conjecture of Propp: for strongly connecte d directed graphs G, delta(G) converges if and only if D-2(G) = D(G). (C) 1997 John Wiley & Sons, Inc.