Graph isomorphism is known to be a difficult computational problem. The problem get even worst if we want to find non-isomorphic graphs in a large family of graphs.

Let us call a (numerical) invariant $\alpha$ is **good** if it is, roughly speaking,

- simple to compute,
- fast to compute, and
- when applied to a family of graphs, say the family $\mathcal{G}_n$ of all graphs of order $\leq n$, the graphs fall into relatively small classes with different $\alpha$-values, that is, $$\lim_{n\ \longmapsto\ \infty}\frac{\max(\text{class sizes})}{\#\mathcal{G}_n}\longrightarrow0.$$

For example, the size of graphs are good invariants as it satisfies the conditions (1), (2), and (3) in the family $\mathcal{G}_n$ of all graphs of order $\leq n$. However, this is not true for the order of graphs in this family. The spectrum can be a candidates in this family, but it is not good in the family of trees.

One technique to overcome the isomorphism problem in large family of graphs is to use good invariants to put graphs into non-isomorphic classes and then try isomorphism check inside each class.

The question is **what are best good invariants?**

11more comments