Finding Optimal Spanning Trees For Damaged Networks

Abstract

We use a representation for the spanning tree where a parent function maps non-root vertices to vertices. Two spanning trees are defined to be adjacent if their function representations differ at exactly one vertex. Given a graph $G$, we show that the graph $H$ with all spanning trees of $G$ as vertices and any two vertices being adjacent iff their parent functions differ at exactly one vertex is connected.