4
$\begingroup$

The title is essentially the question. I know that trees can be represented as a topology (equivalently a topological closure operator) on a set -- so I'm wondering if the collection of spanning trees provides a "topological representation" of a graph (up to labelling of vertices).

Edit: As @dkuper pointed out a "topological" tree depends on the root --- making it more specific than a "graph" tree. I'm a topologist, not a graph theorist, so this is less interesting to me, but I think the question then essentially becomes: "Given a labelling of a graph $G$, when is $G$ the union of of its spanning trees?" A quick Google search doesn't say much, but this "seems" like a simple question.

$\endgroup$
9
  • $\begingroup$ do you put the number of times each tree appears in the collection ? If this information is lost, then the statement is false (with for instace cycle and line of same length). $\endgroup$
    – Denis
    Nov 19, 2013 at 13:17
  • $\begingroup$ The trees would retain the labelling, would that do it? $\endgroup$
    – ihaphleas
    Nov 19, 2013 at 13:24
  • $\begingroup$ It doesn't really make sense, you want to be invariant under relabelling. The question is interesting if you put each tree (up to isomorphism) in your collection, together with its multiplicity. $\endgroup$
    – Denis
    Nov 19, 2013 at 13:25
  • $\begingroup$ Basically, the different trees would be different topologies on the same set of elements. I think we need to retain some idea of how these topologies interact -- not just a count. I just mean, invariant up to coloring blue, for example. Perhaps my terminology for graph theory is not very good -- but does that make some sort of sense? $\endgroup$
    – ihaphleas
    Nov 19, 2013 at 13:42
  • $\begingroup$ could you put a link to this topology via trees that you're referring to ? $\endgroup$
    – Denis
    Nov 19, 2013 at 13:46

1 Answer 1

1
$\begingroup$

I think I can extend my comment into an answer: if the collection of spanning trees includes all trees even if they are isomorphic as graphs but having different labels, then a graph isomorphism will induce an isomorphism on spanning trees and vice-versa. If you include only spanning trees up to graph isomorphism, then no, as example with tetrahedron vs cube shows (or for that matter "v" vs triangle if you disallow distinguishing spanning trees by root node).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .