10
$\begingroup$

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

Improve this question
$\endgroup$
11
  • 4
    $\begingroup$ This question was already asked at: mathoverflow.net/questions/11631/complete-graph-invariants $\endgroup$
    – Gwyn Whieldon
    Commented Jan 15, 2011 at 2:47
  • 6
    $\begingroup$ 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? $\endgroup$
    – Joseph O'Rourke
    Commented Jan 15, 2011 at 14:04
  • 3
    $\begingroup$ Joseph, maybe (or maybe not) the adjacency matrix up to conjugation over $\mathbb Z$ is enough. I have asked this as a separate question: mathoverflow.net/questions/52169/adjacency-matrices-of-graphs $\endgroup$
    – Andreas Thom
    Commented Jan 15, 2011 at 17:05
  • 1
    $\begingroup$ @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. $\endgroup$
    – Hans-Peter Stricker
    Commented Feb 14, 2011 at 7:50
  • 4
    $\begingroup$ 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. $\endgroup$
    – Joel David Hamkins
    Commented Apr 30, 2011 at 11:05

1 Answer 1

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

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