On the tree graph of a connected graph

Ana Paulina Figueroa; Eduardo Rivera-Campo

Discussiones Mathematicae Graph Theory (2008)

  • Volume: 28, Issue: 3, page 501-510
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Ana Paulina Figueroa, and Eduardo Rivera-Campo. "On the tree graph of a connected graph." Discussiones Mathematicae Graph Theory 28.3 (2008): 501-510. <http://eudml.org/doc/270574>.

@article{AnaPaulinaFigueroa2008,
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.},
author = {Ana Paulina Figueroa, Eduardo Rivera-Campo},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {tree graph; property Δ*; property Δ⁺; property ; property },
language = {eng},
number = {3},
pages = {501-510},
title = {On the tree graph of a connected graph},
url = {http://eudml.org/doc/270574},
volume = {28},
year = {2008},
}

TY - JOUR
AU - Ana Paulina Figueroa
AU - Eduardo Rivera-Campo
TI - On the tree graph of a connected graph
JO - Discussiones Mathematicae Graph Theory
PY - 2008
VL - 28
IS - 3
SP - 501
EP - 510
AB - 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.
LA - eng
KW - tree graph; property Δ*; property Δ⁺; property ; property
UR - http://eudml.org/doc/270574
ER -

References

top
  1. [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. Zbl0881.05076
  2. [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. Zbl0528.05019
  3. [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. Zbl0655.05038
  4. [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. Zbl1021.05025
  5. [5] F.J. Zhang and Z. Chen, Connectivity of (adjacency) tree graphs, J. Xinjiang Univ. Natur. Sci. 3 (1986) 1-5. Zbl0645.05031

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.