Let G be a graph and C be a set of cycles of G. The tree graph of G defined by C, is the graph T(G,C) that has one vertex for each spanning tree of G, in which two trees T and T' are adjacent if their symmetric difference consists of two edges and the unique cycle contained in T ∪ T' is an element of C. We give a necessary and sufficient condition for this graph to be connected for the case where every edge of G belongs to at most two cycles in C.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1423,
author = {Ana Paulina Figueroa and Eduardo Rivera-Campo},
title = {On the tree graph of a connected graph},
journal = {Discussiones Mathematicae Graph Theory},
volume = {28},
year = {2008},
pages = {501-510},
zbl = {1173.05014},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1423}
}
Ana Paulina Figueroa; Eduardo Rivera-Campo. On the tree graph of a connected graph. Discussiones Mathematicae Graph Theory, Tome 28 (2008) pp. 501-510. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1423/
[000] [1] H.J. Broersma and X. Li, The connectivity of the of the leaf-exchange spanning tree graph of a graph, Ars. Combin. 43 (1996) 225-231. | Zbl 0881.05076
[001] [2] F. Harary, R.J. Mokken and M. Plantholt, Interpolation theorem for diameters of spanning trees, IEEE Trans. Circuits and Systems 30 (1983) 429-432, doi: 10.1109/TCS.1983.1085385. | Zbl 0528.05019
[002] [3] K. Heinrich and G. Liu, A lower bound on the number of spanning trees with k endvertices, J. Graph Theory 12 (1988) 95-100, doi: 10.1002/jgt.3190120110. | Zbl 0655.05038
[003] [4] X. Li, V. Neumann-Lara and E. Rivera-Campo, On a tree graph defined by a set of cycles, Discrete Math. 271 (2003) 303-310, doi: 10.1016/S0012-365X(03)00132-8. | Zbl 1021.05025
[004] [5] F.J. Zhang and Z. Chen, Connectivity of (adjacency) tree graphs, J. Xinjiang Univ. Natur. Sci. 3 (1986) 1-5. | Zbl 0645.05031