Vertex weights are a metaphor for a constant value $\pi_i$ that is added to the weight of every edge $e_{ij}$ that is adjacent to vertex $v_i$ in a symmetric graph $G(V,E)$ with weighted edges.

The fact that the edge-set of the optimal tour through the vertices of such a graph is invariant under the addition of vertex weights is exploited in the calculation of the Held Karp lower bound for the Traveling Salesman Problem, but apart from that I couldn't find any other algorithms in graph theory that utilize vertex weights.

As all the edge-set of optimal-weight solutions to problems with predefined nominal vertex-degrees are invariant under the additon of vertex weights, it appears to me that the potential of vertex weights hasn't yet been anticipated by algorithm designers.

**Questions:**

- what are examples of algorithms in graph theory that yield improved quality of approximate solutions by means of vertex weights?
- are there any publications whose primary subject is the study of vertex weights?

The reason for asking is that I found a way to *remove* vertex weights from a graph, resp. calculate their value and from experiments I found that the tours reported by heuristics were often up 1% or 2% better after the vertex weights had been removed.