The Dynamics of the Forest Graph Operator
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 T1 and T2 are adjacent if T2 = T1 − e + f for s...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2016-11-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.1901 |
| _version_ | 1827840321450409984 |
|---|---|
| author | Dara Suresh Hegde S.M. Deva Venkateshwarlu Rao S.B. Zaslavsky Thomas |
| author_facet | Dara Suresh Hegde S.M. Deva Venkateshwarlu Rao S.B. Zaslavsky Thomas |
| author_sort | Dara Suresh |
| collection | DOAJ |
| description | 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 T1 and T2 are adjacent if T2 = T1 − e + f for some edges e ∈ T1 and f ∉ T1. 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 N(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 N(G) in which two maximal forests F1, F2 of G form an edge if and only if they differ exactly by one edge, i.e., F2 = F1 − e + f for some edges e ∈ F1 and f ∉ F1. 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 K3 and K1. The F-depth of any graph G different from K3 and K1 is finite. We also determine various parameters of F(G) for an infinite graph G, including the number, order, size, and degree of its components. |
| first_indexed | 2024-03-12T07:32:29Z |
| format | Article |
| id | doaj.art-366fdc434fbd46cab4477f05c69704c4 |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T07:32:29Z |
| publishDate | 2016-11-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-366fdc434fbd46cab4477f05c69704c42023-09-02T21:42:49ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922016-11-0136489991310.7151/dmgt.1901dmgt.1901The Dynamics of the Forest Graph OperatorDara Suresh0Hegde S.M.1Deva Venkateshwarlu2Rao S.B.3Zaslavsky Thomas4Department of Mathematical and Computational Sciences National Institute of Technology Karnataka Surathkal, Mangalore-575025, IndiaDepartment of Mathematical and Computational Sciences National Institute of Technology Karnataka Surathkal, Mangalore-575025, IndiaC.R. Rao Advanced Institute of Mathematics, Statistics and Computer Science Hyderabad-500 046, IndiaC. R. Rao Advanced Institute of Mathematics, Statistics and Computer Science Hyderabad-500 046, IndiaDepartment of Mathematical Sciences, Binghamton University Binghamton, NY, 13902-6000, United States of AmericaIn 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 T1 and T2 are adjacent if T2 = T1 − e + f for some edges e ∈ T1 and f ∉ T1. 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 N(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 N(G) in which two maximal forests F1, F2 of G form an edge if and only if they differ exactly by one edge, i.e., F2 = F1 − e + f for some edges e ∈ F1 and f ∉ F1. 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 K3 and K1. The F-depth of any graph G different from K3 and K1 is finite. We also determine various parameters of F(G) for an infinite graph G, including the number, order, size, and degree of its components.https://doi.org/10.7151/dmgt.1901forest graph operatorgraph dynamics |
| spellingShingle | Dara Suresh Hegde S.M. Deva Venkateshwarlu Rao S.B. Zaslavsky Thomas The Dynamics of the Forest Graph Operator Discussiones Mathematicae Graph Theory forest graph operator graph dynamics |
| title | The Dynamics of the Forest Graph Operator |
| title_full | The Dynamics of the Forest Graph Operator |
| title_fullStr | The Dynamics of the Forest Graph Operator |
| title_full_unstemmed | The Dynamics of the Forest Graph Operator |
| title_short | The Dynamics of the Forest Graph Operator |
| title_sort | dynamics of the forest graph operator |
| topic | forest graph operator graph dynamics |
| url | https://doi.org/10.7151/dmgt.1901 |
| work_keys_str_mv | AT darasuresh thedynamicsoftheforestgraphoperator AT hegdesm thedynamicsoftheforestgraphoperator AT devavenkateshwarlu thedynamicsoftheforestgraphoperator AT raosb thedynamicsoftheforestgraphoperator AT zaslavskythomas thedynamicsoftheforestgraphoperator AT darasuresh dynamicsoftheforestgraphoperator AT hegdesm dynamicsoftheforestgraphoperator AT devavenkateshwarlu dynamicsoftheforestgraphoperator AT raosb dynamicsoftheforestgraphoperator AT zaslavskythomas dynamicsoftheforestgraphoperator |