Given a graph, say one wants to find the clique number, independence number, chromatic number, vertex cover number etc., one knows that a solution exists. However if the solution space has more than one solution, it is possible to talk about the symmetry of the solution space. For instance if there is only one solution, we have only the identity. However, if we have $n!$ solutions, the solution space has $S_n$ as symmetry group ($n$ is number of vertices on the graph).
Has there been any study on the symmetry of solution spaces to NP-complete problems atleast for classes of graphs?
