- Tytuł:
- The Dynamics of the Forest Graph Operator
- Autorzy:
-
Dara, Suresh
Hegde, S.M.
Deva, Venkateshwarlu
Rao, S.B.
Zaslavsky, Thomas - Powiązania:
- https://bibliotekanauki.pl/articles/31340605.pdf
- Data publikacji:
- 2016-11-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
forest graph operator
graph dynamics - Opis:
- 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2016, 36, 4; 899-913
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł