# 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. – Gilles 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. – Stéphane Gimenez Mar 15 '12 at 20:20

## 1 Answer

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}$).

In the case nodes cannot be identified, the (conjectured) hardness of Graph Isomorphism (probably) prevents an efficient, real mapping from Graphs to the naturals; for now, we have to be satisfied with a mapping from graph presentations to naturals---or show considerable genius.

• No, you are assuming that nodes have identities. – Stéphane Gimenez Mar 15 '12 at 20:23
• @StéphaneGimenez That's right. Otherwise I would be likely to solve Graph Isomorphism, which is not known to admit a (deterministic) polynomial time solution. See here. – Raphael Mar 15 '12 at 20:34