# Graph isomorphism by invariants

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,

1. simple to compute,
2. fast to compute, and
3. 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?

• The number of edges is a good invariant too. Jan 25 '19 at 16:22
• I like the (absolute value of the) determinant of the adjacency matrix (for connected graphs). Gerhard "Still Wants Even More Invariants" Paseman, 2019.01.25. Jan 25 '19 at 16:48
• @Wojowu, I think "size" here is being used to mean the number of edges, in contrast to "order" for number of vertices. Jan 25 '19 at 16:58
• Maybe the ordered list of vertex degrees? I think networkx (python graph library) uses that a fast not-isomorphic checker. You might want to check that library for similar functions. (You can turn this into a numerical invariant using an infinite sequence of rationally linearly independent irrational numbers, but this is not good for computing because of precisiob, and I see no reason why not to allow vector valued invariants into your question.) Jan 25 '19 at 18:04
• @Wlod AA Here, $\mathcal{G}_n$ ias considered as the familt of all graph sith at most $n$ vertices, so $\#\mathcal{G}_n=2^{\binom{1}{2}}+\cdots+2^{\binom{n}{2}}$, but once can restrict oneself to just graphs with $n$ vertices too. Jan 26 '19 at 11:03

There is also the question of how the cost scales. An invariant that takes $$n^3$$ time to compute might be great when $$n=20$$, but when $$n=10,000$$ (well within range of modern programs except for very difficult graph classes) $$n^3$$ is too much.