The Dynamics of the Forest Graph Operator

In 1966, Cummins introduced the “tree graph”: the tree graph \( \textbf{T} (G) \) of a graph \( G \) (possibly infinite) has all its spanning trees as vertices, and distinct such trees correspond to adjacent vertices if they differ in just one edge, i.e., two spanning trees \( T_1 \) and \( T_2 \) are adjacent if \( T_2 = T_1 − e + f \) for some edges \( e \in T_1 \) and \( f \notin T_1 \). The tree graph of a connected graph need not be connected. To obviate this difficulty we define the “forest graph”: let \( G \) be a labeled graph of order \( \alpha \), finite or infinite, and let \( \mathfrak{N}(G) \) be the set of all labeled maximal forests of \( G \). The forest graph of \( G \), denoted by \( \textbf{F} (G) \), is the graph with vertex set \( \mathfrak{N}(G) \) in which two maximal forests \( F_1 \), \( F_2 \) of \( G \) form an edge if and only if they differ exactly by one edge, i.e., \( F_2 = F_1 − e + f \) for some edges \( e \in F_1 \) and \( f \notin F_1 \). Using the theory of cardinal numbers, Zorn’s lemma, transfinite induction, the axiom of choice and the well-ordering principle, we determine the F-convergence, F-divergence, F-depth and F-stability of any graph \( G \). In particular it is shown that a graph \( G \) (finite or infinite) is F-convergent if and only if \( G \) has at most one cycle of length 3. The F-stable graphs are precisely \( K_3 \) and \( K_1 \). The F-depth of any graph \( G \) different from \( K_3 \) and \( K_1 \) is finite. We also determine various parameters of \( \mathbf{F} (G) \) for an infinite graph \( G \), including the number, order, size, and degree of its components.