Perfect codes of bi-Cayley graphs (Q6885387)

This paper presents several significant new results on perfect codes in bi-Cayley graphs. A bi-Cayley graph is defined as a graph admitting a semiregular group \(H\) of automorphisms with exactly two vertex orbits. It is further called an algebraically Cayley graph if its full automorphism group contains a regular subgroup \(G\) such that \(H \leq G\). By employing the theory of automorphisms of bi-Cayley graphs, the paper establishes a necessary and sufficient condition for a bi-Cayley graph \(\Gamma\) to be an algebraically Cayley graph. This characterization is then applied to determine the perfect codes in bi-Cayley graphs that are also algebraically Cayley graphs. Notably, the paper reveals a close connection between perfect codes and vertex partitions in regular bi-Cayley graphs. Several equivalent conditions for subsets to form perfect codes in such graphs are provided. As applications, the paper also constructs several families of perfect codes in bi-Cayley graphs.