Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

2 Answers

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?

share|improve this answer
3  
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
2  
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
add comment

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)

share|improve this answer
    
Sounds interesting, at least to find out when and why this invariant might eventually fail. –  Hans Stricker Jan 11 '13 at 18:07
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.