Es un gráfico $G$ completamente determinado (hasta el etiquetado) por sus árboles de extensión?

Question

El título es esencialmente la pregunta. Sé que los árboles pueden ser representados como una topología (equivalentemente un operador de cierre topológico) en un conjunto -- así que me pregunto si la colección de árboles de extensión proporciona una "representación topológica" de un gráfico (hasta el etiquetado de los vértices).

Edición: Como señaló @dkuper un árbol "topológico" depende de la raíz --- haciéndolo más específico que un árbol "gráfico". Soy un topólogo, no un teórico de grafos, por lo que esto es menos interesante para mí, pero creo que la pregunta entonces se convierte esencialmente: "Dado un etiquetado de un grafo $G$ Cuando es $G$ la unión de sus árboles de extensión". Una búsqueda rápida en Google no dice mucho, pero esto "parece" una pregunta sencilla.

Answer 1

Creo que puedo ampliar mi comentario en una respuesta: si la colección de árboles de extensión incluye todos los árboles aunque sean isomorfos como grafos pero con etiquetas diferentes, entonces un isomorfismo de grafos inducirá un isomorfismo en los árboles de extensión y viceversa. Si sólo se incluyen los árboles de extensión hasta el isomorfismo de grafos, entonces no, como muestra el ejemplo del tetraedro frente al cubo (o, para el caso, la "v" frente al triángulo si no se permite distinguir los árboles de extensión por el nodo raíz).