3
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Are there $n$-vertex non-isomorphic graphs with adjacency matrix $A$ and $B$ such that for every $i\in\{1,\dots,n\}$ we can find a bijection between entries of $A^i$ and entries of $B^i$ as (multi)sets? $\endgroup$
    – user76479
    Commented Mar 7, 2016 at 3:38
  • $\begingroup$ @Arul: I'm not sure I understand the question, but two non-isomorphic strongly regular graphs with the same parameters probably answers it. $\endgroup$
    – Brendan McKay
    Commented Mar 7, 2016 at 3:42
  • $\begingroup$ I meant whether there is an example where we can find a bijective map $g_i:A^i→B^i$ considering $A^i$ and $B^i$ as multisets of $n^2$ values at every $i∈{1,…,n}$ when $A$ and $B$ are non-isomorphic? $\endgroup$
    – user76479
    Commented Mar 7, 2016 at 3:57
  • $\begingroup$ @Arul: So you just want the number of entries of each value to be the same in $A^i$ and $B^i$. Strongly-regular graphs will do that. For each $i$, the $(j,k)$ entry in $A^i$ depends only on whether $j$ and $k$ are equal, adjacent, or not-adjacent. Those three values depend only on the strong-regularity parameters $n,k,\lambda,\mu$, not on the graph structure. $\endgroup$
    – Brendan McKay
    Commented Mar 7, 2016 at 8:10
  • 1
    $\begingroup$ @Arul: See arxiv.org/abs/1301.1493 for the most successful practical methods. $\endgroup$
    – Brendan McKay
    Commented Mar 10, 2016 at 22:19

You must log in to answer this question.