Name
Abstract | ||
|---|---|---|
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 epsilon is an element of E T-1 and f is not an element of 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 a, 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 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 is an element of F-1 and f is not an element of 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 F(G) for an infinite graph G, including the number, order, size, and degree of its components. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.7151/dmgt.1901 | DISCUSSIONES MATHEMATICAE GRAPH THEORY |
Keywords | Field | DocType |
forest graph operator,graph dynamics | Discrete mathematics,Combinatorics,Vertex-transitive graph,Edge-transitive graph,Graph power,Cubic graph,Cycle graph,Regular graph,Degree (graph theory),Distance-regular graph,Mathematics | Journal |
Volume | Issue | ISSN |
36 | 4 | 1234-3099 |
Citations | PageRank | References |
0 | 0.34 | 6 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| suresh dara | 1 | 0 | 0.34 |
| S. M. Hegde | 2 | 32 | 9.96 |
| venkateshwarlu deva | 3 | 0 | 0.34 |
| s b rao | 4 | 0 | 0.34 |
| T. Zaslavsky | 5 | 297 | 56.67 |