Iterating the branching operation on a directed graph

The branching operation D, defined by Propp, assigns to any directed graph G another directed graph D(G) whose vertices are the oriented rooted spanning trees of the original graph G. We characterize the directed graphs G for which the sequence δ(G) = (G, D(G), D²(G),…) converges, meaning that it is eventually constant. As a corollary of the proof we get the following conjecture of Propp: for strongly connected directed graphs G, δ(G) converges if and only if D²(G) = D(G). © 1997 John Wiley & Sons, Inc.