PDF
Discussiones Mathematicae Graph Theory 28(3) (2008)
501-510
DOI: https://doi.org/10.7151/dmgt.1423
ON THE TREE GRAPH OF A CONNECTED GRAPH
| Ana Paulina Figueroa
Instituto de Matemáticas | Eduardo Rivera-Campo
Departmento de Matemáticas |
Abstract
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.Keywords: tree graph, property Δ*, property Δ+.
2000 Mathematics Subject Classification: 05C05.
References
| [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. |
| [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. |
| [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. |
| [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. |
| [5] | F.J. Zhang and Z. Chen, Connectivity of (adjacency) tree graphs, J. Xinjiang Univ. Natur. Sci. 3 (1986) 1-5. |
Received 12 February 2008
Revised 18 June 2008
Accepted 18 June 2008
Close