# Invariants that might determine graph up to isomorphism

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

• This question was already asked at: mathoverflow.net/questions/11631/complete-graph-invariants Jan 15, 2011 at 2:47
• 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? Jan 15, 2011 at 14:04
• 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 Jan 15, 2011 at 17:05
• @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. Feb 14, 2011 at 7:50
• 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. Apr 30, 2011 at 11:05