Question

Assuming that there are no known complete graph invariants in the spirit of Harrsion's question that do not depend on any labelling (see graph property at Wikipedia), I wonder if there are graph invariants that are

• almost complete, i.e. discriminating almost all finite graphs up to isomorphism
• almost complete in a weaker sense, i.e. discriminating all finite graphs except for a small, but finite fraction (the smaller the fraction the greater the invariant's discriminating power)
• probably complete, i.e. not proven to be incomplete yet (e.g. by counterexamples)

Can anyone provide examples or references?

Answer 1

I'm not sure I understand the question well enough to know whether this is a reasonable answer. But a standard observation concerning the graph isomorphism problem is that there is an approach that feels as though it almost works: work out the eigenvalues and eigenvectors of the adjacency matrix.

There is a small technical problem that you can't do this exactly, and a more fundamental problem that if you have eigenvalues of multiplicity greater than 1 then you don't distinguish all graphs. But I would guess that almost all graphs have adjacency matrices with distinct eigenvalues. Can anyone confirm this? And if that is the case, does it answer your question?

Answer 2

Though painfully slow to compute, I've yet to find a counterexample to the first invariant proposed in this paper by Mehendale: a vector of integers counting, for each n, the number of labeled subgraphs of G which are trees on n vertices.

Update: I've since discovered several counterexamples, perhaps the simplest being

S3 U P2 U P2

and

P4 U P3 U P1

both of which yield the signature (8,5,3,1)