Suppose for a graph $G=(V,E)$ and a spanning tree T of G, $\Delta(T)$ is the largest degree of a vertex in T, and let $\Delta^*$ be the smallest such quantity over all spanning trees of $G$.

We have the following local search procedure which can changes spanning tree $T$ into a different spanning tree $T'$: We find an edge $e$ not in $T$ and add it to $T$. This results in a cycle $C$ - call its vertices vertices $V(C)$. We then delete an edge in $C$ incident to a vertex in $V(C)$ with highest degree.

My question is this: if $\Delta(T) > \Delta^*$, can we always find an edge $e$ to add, such that the maximum degree of vertices in $V(C)$ is strictly less in $T'$ than it is in $T$?

  • $\begingroup$ How about just using a greedy approach, modifying Prim's algorithm to add an edge according to minimal degree of the origin vertex? I suspect that that will give minimal maximal degree... $\endgroup$ – vonbrand Nov 22 '15 at 1:46
  • $\begingroup$ You can edit your question by clicking the "edit" button underneath the question. If you've created two accounts, I encourage you to merge them using the instructions here. This should enable you to regain access to the question, and ensure you receive notifications about answers and comments. $\endgroup$ – D.W. Nov 22 '15 at 2:20
  • 1
    $\begingroup$ For editing and commenting on your own posts, you should register your account. When you do so, you can request SE staff to merge your registered account with this one. (cc @D.W.) $\endgroup$ – Raphael Nov 22 '15 at 8:48

No, we cannot.

An counterexample to local search to find minimum degree spanning tree

Here is an counterexample. Let $G$ be the 3-regular graph on the right side that has 14 vertices and 21 edges. Let $T$ be the spanning tree that consists of all the edges in bold. That is, $T$ has all the edges in $G$ except the innermost 7 edges and the right topmost one edge. The graph on the left side shows a hamiltonian path of $G$. That is, $\Delta(T)=3$ and $\Delta^*=2$.

Let $e$ be an edge not in $T$. If we add $e$ to $T$, the resulting cycle $C$ contains at least two non-adjacent vertices of degree 3 in $T$. If we further delete any edge in $C$ incident to a vertex in $C$ with the highest degree 3, we obtain graph $T'$. There is at least one vertex of degree 3 in $T'$. That is, the maximum degree of vertices in $V(C)$ in $T'$ is 3.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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