Roughly speaking, we are trying to find complete graph invariant
as the lexicographically first matrix from the permutations
of the adjacency matrix.


Let $G$ be graph, possibly directed graph, of order $n$ and adjacency matrix $A_G$.

Let $P$ be matrix with entries variables $x_{i,j}$.
Add the linear integer constraints $P$ to be permutation matrix:
$x_{i,j}$ are non-negative and each row and each column sum to $1$.

Define $f(i,j)=2^{i n + j}$. 

Let $B=P A_G$. The entries of $B$ are linear equations in the variables
of $P$.

Take the optimization problem:

$F(G) =\text{ minimize } \sum_{0 \le i,j \le n-1} f(i,j) B[i,j]$.

> Is the above integer linear program complete graph invariant,
i.e. $F(G)=F(H)$ iff $G,H$ are isomorphic?

For all subsets $i,j$ with $B[i,j]=1$ the sums $f(i,j)B[i,j]$ are distinct.

We believe the RHS of $F(G)$ is bijection matrix with 0-1 entries and
the integers $[0,2^{n^2-1}]$.

> In case of negative answer can we take $B=P A_G P^{-1}=P A_G P^T$ and get quadratic
integer program?


**Added**

We did experiments on small graphs. The approach $B=P A_G$ doesn't
work, but the approach $B=P A_G P^T$ works on the tested graphs.

Since we don't have solver for optimizing quadratic function,
we enumerated the permutations.

Here is sage code that can be run in a browser.

    def mafai(g):
    	n=g.order()
    	mi=oo
    
    	A=g.adjacency_matrix()
    
    	for pe in Permutations(n):
    		P=pe.to_matrix()
    		B=P*A*P.transpose()
    		su=0
    		for i in xrange(n):
    			for j in xrange(n):
    				su += B[i,j]*2**(i*n+j)
    		mi=min(su,mi)		
    	return mi