5
$\begingroup$

Let $G$ be a connected graph on $n$ vertices and $\mathcal{T}$ be the set of all spanning trees of $G$.

Consider the graph whose vertices are the elements of $\mathcal{T}$ and

$T, T' \in \mathcal{T}$ are connected by an edge if $|E(T)\cap E(T')| = n - 2 $

Does this graph have a name?

One can see that the graph is connected. Are any of its other properties known?

Is there any literature on this graph?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
7
$\begingroup$

I have seen this called the Tree Graph of $G$. It has been investigated by a lot of authors. For example Cummings proved in "Hamilton circuits in tree graphs" IEEE Trans. Circuit Theory,13(1966), pp.82-90, that this graph is Hamiltonian. Holzmann and Harary generalized this to tree graphs of matroids in "On the Tree Graph of a Matroid".

Improve this answer
$\endgroup$
3
$\begingroup$

Don't know about a name, but for starters see Lovasz "A homology theory for the spanning trees of a graph" http://www.cs.elte.hu/~lovasz/scans/homology-span-tree.pdf

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.