2
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – j.c.
    Apr 22, 2010 at 22:37

2 Answers 2

Reset to default
5
$\begingroup$

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?

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ 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. $\endgroup$
    – Gordon Royle
    Apr 23, 2010 at 1:03
  • 2
    $\begingroup$ Almost all graphs are not trees. But if two random trees are iso-spectral with positive probability then that is not so satisfying. $\endgroup$
    – Aaron Meyerowitz
    Jan 11, 2013 at 20:50
0
$\begingroup$

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)

Improve this answer
$\endgroup$
1
  • $\begingroup$ Sounds interesting, at least to find out when and why this invariant might eventually fail. $\endgroup$
    – Hans-Peter Stricker
    Jan 11, 2013 at 18:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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