Geodesic
The Dynamics of the Forest Graph Operator
Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 4, pp. 899-913.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: forest graph operator, graph dynamics 
@article{DMGT_2016_36_4_a10,
     author = {Dara, Suresh and Hegde, S.M. and Deva, Venkateshwarlu and Rao, S.B. and Zaslavsky, Thomas},
     title = {The {Dynamics} of the {Forest} {Graph} {Operator}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {899--913},
     publisher = {mathdoc},
     volume = {36},
     number = {4},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a10/}
}
TY  - JOUR
AU  - Dara, Suresh
AU  - Hegde, S.M.
AU  - Deva, Venkateshwarlu
AU  - Rao, S.B.
AU  - Zaslavsky, Thomas
TI  - The Dynamics of the Forest Graph Operator
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2016
SP  - 899
EP  - 913
VL  - 36
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a10/
LA  - en
ID  - DMGT_2016_36_4_a10
ER  - 
%0 Journal Article
%A Dara, Suresh
%A Hegde, S.M.
%A Deva, Venkateshwarlu
%A Rao, S.B.
%A Zaslavsky, Thomas
%T The Dynamics of the Forest Graph Operator
%J Discussiones Mathematicae. Graph Theory
%D 2016
%P 899-913
%V 36
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a10/
%G en
%F DMGT_2016_36_4_a10
Dara, Suresh; Hegde, S.M.; Deva, Venkateshwarlu; Rao, S.B.; Zaslavsky, Thomas. The Dynamics of the Forest Graph Operator. Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 4, pp. 899-913. http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a10/

[1] H.J. Broersma and X. Li, The connectivity of the leaf-exchange spanning tree graph of a graph, Ars Combin. 43 (1996) 225-231.

[2] R. Cummins, Hamilton circuits in tree graphs, IEEE Trans. Circuit Theory CT-13 (1966) 82-90. doi: 10.1109/TCT.1966.1082546

[3] K.Ch. Das, A.S. Cevik and I.N. Cangul, The number of spanning trees of a graph, J. Inequal. Appl. 2013 (2013) article 395, 13 pages.

[4] K.Ch. Das, A sharp upper bound for the number of spanning trees of a graph, Graphs Combin. 23 (2007) 625-632. doi: 10.1007/s00373-007-0758-4

[5] R. Diestel, Graph Theory, Third Edition, Graduate Texts in Mathematics, Volume 173 (Springer, Heidelberg, 2005).

[6] L. Feng, K. Xu, K.Ch. Das, A. Ilić and G. Yu, The number of spanning trees of a graph with given matching number, Int. J. Comput. Math. 93 (2016) 837-843. doi: 10.1080/00207160.2015.1021341

[7] L. Feng, G. Yu, Z. Jiang and L. Ren, Sharp upper bounds for the number of spanning trees of a graph, Appl. Anal. Discrete Math. 2 (2008) 255-259. doi: 10.2298/AADM0802255F

[8] G.R. Grimmett, An upper bound for the number of spanning trees of a graph, Dis- crete Math. 16 (1976) 323-324. doi: 10.1016/S0012-365X(76)80005-2

[9] E. Kamke, Theory of Sets (Courier, 1950).

[10] J. Li, W.C. Shiu and A. Chang, The number of spanning trees of a graph, Appl. Math. Lett. 23 (2010) 286-290. doi: 10.1016/j.aml.2009.10.006

[11] G. Liu, On connectivities of tree graphs, J. Graph Theory 12 (1988) 453-459. doi: 10.1002/jgt.3190120318

[12] E. Prisner, Graph Dynamics (CRC Press, 1995).

[13] J. Rodriguez and L. Petingi, A sharp upper bound for the number of spanning trees of a graph, in: Proceedings of the Twenty-Eighth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, Fla., 1997), Congr. Numer. 126 (1997) 209-217.

[14] H. Shank, A note on Hamilton circuits in tree graphs, IEEE Trans. Circuit Theory CT-15 (1968) 86-86. doi: 10.1109/TCT.1968.1082765

[15] D.V.V.P.R.V.B. Suresh, V. Deva and S.B. Rao, Dynamics of spanning tree graph operator, in: International Congress of Mathematicians ICM 2010, Short Communications Abstracts Book (Hindustan Book Agency, 2010) 472-473.

[16] Y. Teranishi, The number of spanning forests of a graph, Discrete Math. 290 (2005) 259-267. doi: 10.1016/j.disc.2004.10.014

[17] H. Whitney, 2-isomorphic graphs, Amer. J. Math. 55 (1933) 245-254. doi: 10.2307/2371127

[18] F.J. Zhang and Z. Chen, Connectivity of (adjacency) tree graphs, J. Xinjiang University (Natural Science) 3 (1986) 1-5.

[19] X.-D. Zhang, A new bound for the complexity of a graph, Util. Math. 67 (2005) 201-203.