MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Tree graph restructuring.

I have a graph $G(V,E)$ and a tree $T(V',E')$ where $|V|=|V'|$ and $T$ is isomorphic to a subgraph of $G$. In other words I found a spanning tree of $G$ and made one of its nodes act as the root.

I now have 2 problems I want to look at:

1. If I remove a node from $G$ what is the optimal way to determine if a new $T$ exits and if so find it. 2.Assume $v_0$ is the root of $T$. I'm given an arbitrary node $v_i$ and need to find a new $T$ in which $v_i$ is the root.

I would like to know what (if any) literature or solutions already exist for these problems?

I am asking this question because I am working on a project involving network topologies and would like to know about any existing solution (especially if they have proofs) before I start trying to solve the problem on my own.

-

 The paper does seem to be what I'm looking for (haven't read past the intro yet) but the rerooting link is not. they assume that nodes are being deleted from the tree, however in my case no nodes are being removed the root is simply being switched to a different node requiring a restructuring of who is a parent node and who is a child node. – njwizz Oct 9 2011 at 20:18 The case where the existing root is not being deleted is straightforward: simply reverse the parent-child relationship between the new node and its extant parent. The new root and the old root cannot share any descendants, because then there would have been a cycle in the tree. In the directed case, add a path from $v_i$ to $v_o$ to $T$, remove the link from the parent of $v_i$ to $v_i$ and break any cycles created. – Chad Musick Oct 9 2011 at 20:42