Here I try to seek if restricting the structure of permutations would still keep GI property.


Given a $2n$ vertex undirected graph whose vertices are partitioned arbitrarily in pairs to say WLOG $(1,2)$, $(3,4)$, $\dots$, $(2n-1,2n)$. Call these vertices pairs as super vertices.


Call two such graphs $2n$ vertex labelled graphs $G$, $H$ whose adjacencies are $A$ and $B$ respectively $\mathsf{vertex}$-$\mathsf{pair}$-$\mathsf{isomorphic}$ iff 


**($\star$)** there is a permutation $P$ such that $A=PBP'$ on the condition that the permutation $P$ permutes only supervertices.


Note that only a subset $n!$ of permutations of $(2n)!$ allowed. 


In particular, 


**($\star$)** vertex $2i$ in $G$ is mapped to vertex $2j$ in $H$ by the permutation iff vertex $2i-1$ in $G$ must be mapped to $2j-1$ in $H$.


Is $\mathsf{vertex}$-$\mathsf{pair}$-$\mathsf{isomorphic}$ $\mathsf{GI}$-$\mathsf{complete}$?


Also posted: <https://cs.stackexchange.com/questions/53824/restricting-possible-permutations-in-graph-isomorphism-problem>



A possible GI isomorphic problem
It is GI-complete. Take two arbitrary connected graphs with degrees at least 2 (obviously a GI-complete class). For each vertex $v$, add a new vertex $v'$ and join it only to $v$. The pairs $\{v,v'\}$ have the property you describe.


