# An indexing function for graphs

Definition from wikipedia:

A graph is an ordered pair $G = (V, E)$ comprising a set $V$ of nodes together with a set $E$ of edges, which are two-element subsets of $V$.

The set of all finite graphs (modulo isomorphism: we don't want nodes to have identities) is countable and could be enumerated. But what would be an efficient (low-complexity, from a programming point of view) injection from graphs to $\mathbb{N}$?

Edit: Gilles' comment indicates that it is not know whether there is a such function feasible in polynomial time. An example of an exponential-complexity function would be good enough; we can surely do better than a brute enumeration?

• Interesting question, given that no polynomial algorithm is known for deciding graph isomorphism. Mar 15 '12 at 20:12
• Just a guess: As graphs can be represented by adjacency or incidence matrices it is perhaps easier to look for suitable encoding of the matrix that represents the graph.
– uli
Mar 15 '12 at 20:14
• @uli: Yes but in this case the result must stable by permutation of the indexes that have been assigned to nodes. Mar 15 '12 at 20:20

A graph $G$ whose nodes are numbered is uniquely described by its adjacency matrix. Concatenating the matrix's rows yields a natural number $\cal{G}$ in binary representation; in order to deal with leading $0$, prepend a $1$. This mapping is obviously injective. For easier decoding, you might want to use Cantor's pairing function on $(\cal{G}, |V|)$ and use the result as graph number.
Computing this mapping is easy, but the resulting number can be huge ($\approx 2^{|V|^2}$).