×

On the tree graph of a connected graph. (English) Zbl 1173.05014

Summary: 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\cup 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\).

MSC:

05C05 Trees
05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: DOI Link