Let $V = (v\_1,...,v\_n)$ be a set of vertices for a directed graph. We denote an edge between the two vertices $v\_i$ and $v\_j$ by $(i,j)$. The edge set $E$ for a graph $(V,E)$ is then a set of tuples $E \in P(\{(i,j) \mid i,j \in \{1,...,n\}\})$.


My Question is if for fixed $n \in \mathbb{N}$ we can efficiently define a map
$$
F\_n : P(\{(i,j) \mid i,j \in \{1,...,n\}\}) \rightarrow \mathbb{R}
$$
such that $F\_n(E)=F\_n(E')$ if and only if the two Graphs are the same modulo permutation of vertices, i.e. if there exists a permutation $\sigma \in S\_n$ such that $E = \{(\sigma(i),\sigma(j)) \mid (i,j) \in E'\}$.


Such a map should be relatively simple to construct with sums over all permutations. I am interested in simpler known invariants, which would ideally require less than $\mathcal{O}(n!)$ amount of work to calculate.


I'm new to graph-theory and thought someone must have already thought about this, since it is fundamental to classifying graphs. Any references or pointers in the right direction are much appreciated.



Is there a permutation invariant for graphs?
You are essentially asking about the graph isomorphism problem. Or, more precisely, you are asking about canonical representation of graphs. There is a huge literature about this. See <https://en.wikipedia.org/wiki/Graph_canonization>.


