,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}$


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$?
  • $\begingroup$ There's a simple objection to Q2: just set $|V|=3$ and $k=1$. $\endgroup$ – Bullet51 Feb 24 at 15:54
  • $\begingroup$ @Bullet51 good point! I will edit my question accordingly to rule out failure due to non-existence $\endgroup$ – Manfred Weis Feb 24 at 17:38

Your Answer

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

Browse other questions tagged or ask your own question.