The Dynamics of the Forest Graph Operator

Dara, Suresh  ; Hegde, S.M. ; Deva, Venkateshwarlu ; Rao, S.B. ; Zaslavsky, Thomas

Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 4, pp. 899-913

Résumé

In 1966, Cummins introduced the “tree graph”: the tree graph 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 ∈ T_1 and f ∉ 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 α, finite or infinite, and let 𝔑(G) be the set of all labeled maximal forests of G. The forest graph of G, denoted by F (G), is the graph with vertex set 𝔑(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 ∈ F_1 and f ∉ 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 𝐅 (G) for an infinite graph G, including the number, order, size, and degree of its components.

Détail

Keywords: forest graph operator, graph dynamics