There are certain graph theoretic problems (especially optimization problems), whose solution-subgraph (i.e. the set of vertices and edges)), is invariant under certain modifications (especially modifications of edge weights) of which some examples are

the set of edges constituting to the shortest paths between a pair of vertices does not change if all edge weights are

*multiplied*by a positive factor; it may however change, if a constant value is*added*to each edge-weight.the set of edges constituting to a minimum spanning tree doesn't change after multiplying the weights with a positive factor and/or adding a constant value; it may however change, if the transformation is only applied to the weights of edges that are adjacent to some given vertex (e.g. after adding "node weights")

the set of edges constituting to either the shortest Hamilton cycle as well as the one constituting to the minimum weight maximal matching, are invariant to changes of "node weights"

the last example is special in that an NP-hard problem and an efficiently solvable problem are apparently invariant under the same kind of edge-weight modifications.

I would like to know, if those kinds of invariants have already been investigated in the spirit of an "Erlangen Program".

$$ $$
**Addendum**

David's example of a shortest-path preserving transformation makes clear, that the algorithm that is used to calculate the shortest path may also play a role in the definition of invariance.

There seem to be *"strongly" invariant* transformations that preserve the solution subgraph under *every* algorithm that determines that same subgraph in the unmodified graph and, also *"weekly" invariant* transformations that depend on the underlying algorithm.

That observation may also indicate, that a classification of algorithms based on the solution-set preserving transformations they support is also an interesting aspect of characterising the invariants of graph transformations.

utilized, but are themselves not in the focus of interest (my perception) but rather play the role of tools. I bet that not very many people (including me) were aware of your examples of transformations. $\endgroup$ – Manfred Weis Dec 30 '15 at 8:01