10

Are there any graph invariants which have a reasonable chance of capturing the graph up to isomorphism? In other words, some candidates for a function $f$ such that $f(G)=f(H)$ if and only if $G$ and $H$ are isomorphic.

For instance, in the case of trees, weighted graph polynomial ($U$-polynomial) of Welsh/Noble 1999 is a candidate because no counter-example has been found. Are there such candidates for general graphs?

Clarification: I'm interested in examples of functions which capture some graph invariant, are practical to compute, and are not yet proven to assign the same value to a pair of non-isomorphic graphs

Sergiy Kozerenko
  • 737
Yaroslav Bulatov
  • 2,380
  • 4
    This question was already asked at: http://mathoverflow.net/questions/11631/complete-graph-invariants – Gwyn Whieldon Jan 15 '11 at 02:47
  • Useful link, thanks. It's different from this question because it asks for for functions which are known to distinguish graphs up to isomorphism, whereas I'm asking for ones which are not known to NOT distinguish graphs up to isomorphism, ie, the ones which could use a counter-example – Yaroslav Bulatov Jan 15 '11 at 03:47
  • Has anyone looked at the purported proof of $GI\in P$ at http://arxiv.org/abs/0711.2010 ? I just discovered it about 30 minutes ago, I checked part 2 and lemma 1 without finding any problems. –  Jan 15 '11 at 03:52
  • 6
    A related question that occurred to me: It is known that there are non-isomorphic but isospectral graphs. What properties in addition to the spectrum might determine graphs up to isomorphism? – Joseph O'Rourke Jan 15 '11 at 14:04
  • 3
    Joseph, maybe (or maybe not) the adjacency matrix up to conjugation over $\mathbb Z$ is enough. I have asked this as a separate question: http://mathoverflow.net/questions/52169/adjacency-matrices-of-graphs – Andreas Thom Jan 15 '11 at 17:05
  • @Andreas: Thanks for posting the separate question; it was interesting constructing the example that shows that conjugacy over $\mathbb Z$ is strictly weaker than isomorphism.

    @Ricky: If I have correctly understood the intended idea in the preprint, the proposed Algorithm 1 will always return "isomorphic" for a pair of isospectral both of which have vertex-transitive symmetry. Such a pair is not always isomorphic; for example, add the increasing-even and increasing-odd 6-cycles to either the single cycle 1-12 (to get the 6th antiprism) or to the three cycles 1-4, 5-8, and 9-12.

     – Tracy Hall Jan 20 '11 at 22:50
  • 1
    @Ricky: If you are still interested: The author admitted in private communication that there was an error in his proof/algorithm: it fails distinguishing strongly regular cospectral graphs. – Hans-Peter Stricker Feb 14 '11 at 07:50
  • 4
    You don't say so, but I think the question is just about finite graphs. If one allows countable graphs, then the collection of graphs forms a standard Borel space, but there can be no Borel function from this space into the reals (or any other standard Borel space) that gives the same value to isomorphic graphs and different values to non-isomorphic graphs. In other words, the graph-isomophism relation relation does not reduce to equality in the sense of Borel equivalence relation theory. – Joel David Hamkins Apr 30 '11 at 11:05
  • 1
    In other words, there is no Borel way (and therefore no completely explicit way) to assign countable objects to countable graphs in such a way that they form a complete invariant. – Joel David Hamkins Apr 30 '11 at 12:11
  • yes, just finite graphs – Yaroslav Bulatov May 02 '11 at 18:19
  • re HS comment, it would be good if the author of the paper updates it to state the error and extract anything else useable from the framework. otherwise there may be further questions – vzn Dec 14 '14 at 03:27

1 Answers1

7

In some ways, provably, no (assuming the graphs are infinite). See MR1011177 (91f:03062) Friedman, H; Stanley, L; "A Borel reducibility theory for classes of countable structures." J. Symbolic Logic 54 (1989), no. 3, 894–914.

This paper shows (although the argument is terse, and at least some is older folklore) that any Borel (in an appropriate sense) function f mapping graphs to any thing else with an equivalence relation E in such a way that G is isomorphic to H iff f(g) E f(H) must be at least as complicated as the graphs themselves.

For a similar result on finite graphs, see MR2135387 (2006e:03049) Calvert, Cummins, Knight, and Miller, Comparing classes of finite structures. (Russian) Algebra Logika 43 (2004), no. 6, 666--701, 759; translation in Algebra Logic 43 (2004), no. 6, 374–392.

Wesley Calvert
  • 119
  • 1
  • 4