Return to Question

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?

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

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 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?

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?