# Limit Behavior of a Graph Iteration

,Let $$G(V,E)$$ be a weighted complete graph.

Let further $$\min_k(v_i)$$ denote, depending on whether the context is arithmetic or set theoretic, either the set of the $$k$$ smallest edges adjacent to $$v_i$$ or their weight-sum; with an overbar it denotes half the arithmetic mean, i.e. $$\overline{\min_k(v)} := \frac{\min_k(v)}{2k}$$

Question:

Defining the following two steps

• for every vertex calculate $$\pi(v) = -\overline{\min_k(v)}$$ as its potential
• for every edge $$e_{uv}$$ set $$w_{uv}=w_{uv}+\pi(u)+\pi(v)\$$ where $$w_{uv}$$ denotes the corresponding edge-weight

as an iteration, what will happen to the set $$\cup_{v\in V}\min_k(v)$$ of edges, if the iteration is carried out indefinitely

• will it converge unconditionally?
• if yes, will the graph induced by the limit set of edges in $$\cup_{v\in V}\min_k(v)$$ be $$k$$-regular, provided a k-regular spanner exists in $$G$$?
• There's a simple objection to Q2: just set $|V|=3$ and $k=1$. – Bullet51 Feb 24 at 15:54
• @Bullet51 good point! I will edit my question accordingly to rule out failure due to non-existence – Manfred Weis Feb 24 at 17:38