Completely Positive formulation of the Graph Isomorphism Problem

Given two graphs $G_1$ and $G_2$ on $n$ vertices each, we define a graph $G$ on vertex set $V_1\times V_2$ and the edge set as the union of edges of $G_1\times \overline{G_2}$, $\overline{G_1}\times G_2$, ${(v,u’),(v,u"))(|u’,u"\in V_2}$foreach$v\in V_1$,and${((u’,v),(u",v))|u’,u"\in V_1}$foreach$v\in V_2$\mathrm{.}Weconsiderthecompletely-positiveLov\acute{a}sz$\vartheta$ function, i.e., $cp\vartheta$ function for $G$. We show that the function evaluates to $n$ whenever $G_1$ and $G_2$ are isomorphic and to less than $n-1\mathrm{/}(4n^4)$ when non-isomorphic. Hence this function provides a test for graph isomorphism. We also provide some geometric insight into the feasible region of the completely positive program.