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

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

share|improve this question
3  
This question was already asked at: mathoverflow.net/questions/11631/complete-graph-invariants –  Gwyn Whieldon Jan 15 '11 at 2:47
5  
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
2  
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 –  Andreas Thom Jan 15 '11 at 17:05
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 Stricker Feb 14 '11 at 7: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 Answer 1

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.

share|improve this answer

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.