There are two problems to solve : firstly writing out a graph as a string (not so hard) and secondly making that identifier unique (very hard!).
There are various 'line notations' used in chemistry that might be suitable to your graphs. You seem to have vertex colors (the numbers 2, 3, 5, 8 in your example) but not edge colors, so it's slightly simpler.
I'm not sure how readable they will be. That depends on how large the graphs are of course. For example, this is the 'signature' of a cage-like molecule:
[C]([C]([C,2]([C]([C,3][C,4]))[C]([C,5][C,3]([C,6]([C,1]))))[C]([C]([C,7][C]([C,1][C,8]))[C,5]([C,8]([C,6])))[C]([C,2][C,7]([C,4]([C,1]))))
Perhaps I chose a particularly complex example, but still.
The second part is harder, but the good news is that you could just use an existing library to do it. One algorithm to do what is often called 'canonical labelling' (see also this page ) is partition refinement, for which one major implementation is nAUTy/traces.
For partition refinement, the vertex colors form the initial partition of the vertices. This partition is then refined until each vertex has a different unique label. A much simpler algorithm that is kind of related (that only works for non-regular graphs) is Morgan numbering. Roughly it goes:
- Label the vertices with a starting value
- Iteratively update the labels based on the labels of the neighbours of each vertex
- Stop when the set of different labels is stable
Hmmm. Actually reading this blogpost it looks like the algorithm is more complex than that. However, for your example, we get:
$$\begin{array}{c|c|c}
& \text{L0} & \text{L1} & \text{L2} \\ \hline
\text{Vertex 1} & 3 & 11 & 27 \\ \hline
\text{Vertex 2} & 8 & 16 & 40 \\ \hline
\text{Vertex 3} & 5 & 23 & 69 \\ \hline
\text{Vertex 4} & 2 & 15 & 53 \\ \hline
\text{Vertex 5} & 8 & 15 & 53 \\ \hline
\end{array}$$
where you can see that vertices 4 and 5 (at the bottom of your diagram on the left) end up with the same value. Using these vertex equivalence classes, we can make a canonical labelling.