# Almost or probably complete graph invariants?

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?

-
A program that one of my friends used for graph isomorphism is "nauty" cs.anu.edu.au/~bdm/nauty . Not sure exactly what goes into it (nor have I used it personally) so I'm not writing this up as an answer, but there are references on that webpage. – j.c. Apr 22 '10 at 22:37

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)

-
Sounds interesting, at least to find out when and why this invariant might eventually fail. – Hans Stricker Jan 11 '13 at 18:07

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?

-
AFAIK it is still unsolved as to whether almost all graphs are distinguished by their spectrum; I think Willem Haemers has conjectured this, at least in conversation, and perhaps also in print. – Gordon Royle Apr 23 '10 at 1:03
Almost all graphs are not trees. But if two random trees are iso-spectral with positive probability then that is not so satisfying. – Aaron Meyerowitz Jan 11 '13 at 20:50