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: http://cs.stackexchange.com/questions/53824/restricting-possible-permutations-in-graph-isomorphism-problem

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

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,

(1) the permutation must map even-numbered vertices in $G$ to even-number vertices in $H$ and

(2) 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: http://cs.stackexchange.com/questions/53824/restricting-possible-permutations-in-graph-isomorphism-problem

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: http://cs.stackexchange.com/questions/53824/restricting-possible-permutations-in-graph-isomorphism-problem