On the BCI problem (Q7295083)

The authors' main aim is to investigate the relationship between the symmetries of the Cayley digraph of a group \(G\) and other graphs and digraphs arising from different actions of \(G\), as well as similar relationships for problems that depend on symmetries. It is well known that the isomorphism problem for Cayley digraphs depends on a property of its automorphism group. The bi-Cayley isomorphism problem (BCI problem) asks whether two Haar graphs of a group \(G\) are isomorphic by a specific list \(\mathcal L\) of maps. The authors show that the Cayley isomorphism problem can be generalized in at least two ways, and that the list of maps of the current BCI problem is not a shortest list of natural maps to check for isomorphism, but is shorter than in the sense that the shortest list of elements that normalize the natural semiregular subgroup isomorphic to a group \(G\) that is contained in the automorphism group of a Haar graph of \(G\). They also develop similar results to reduce the isomorphism problem of Haar graphs of \(G\) to conjugacy classes of semi-regular subgroups of \(G\) in their automorphism groups. Then they consider the isomorphism problem for the first three families, reducing it to the isomorphism problem for related quotients, subgraphs, or Cayley digraphs. They establish that the isomorphism problem for Haar graphs of abelian groups of odd order whose connection set is self-inverse does not reduce the ABCI problem to the CI problem. They remark that there are two obstacles to this, with the obstacles coming from graphs that have twins or are disconnected.