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.
    Commented 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
    Commented 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
    Commented 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
    Commented Jan 11, 2013 at 18:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .