Perfect codes of bi-Cayley graphs

DOI10.1016/J.JCTA.2025.106079MaRDI QIDQ6885387zbMATH OpenFDO

Authors Yan Wang, Kai Yuan, Jianxun Li

Publication date 11 December 2025

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.JCTA.2025.106079

zbMATH Keywords

algebraically Cayley graphbi-Cayley graphperfect

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Finite automorphism groups of algebraic, geometric, or combinatorial structures (20B25) Combinatorial codes (94B25)

Review text

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.

Cites work

• Characterization of subgroup perfect codes in Cayley graphs
• Cyclic Haar graphs
• Domination and efficient domination in cubic and quartic Cayley graphs on abelian groups
• Existence of efficient total dominating sets of circulant graphs of degree 4
• Independent perfect dominating sets in semi-Cayley graphs
• Independent perfect domination sets in Cayley graphs
• Perfect codes in circulant graphs
• Perfect codes in graphs
• Subgroup perfect codes in Cayley sum graphs
• The automorphisms of bi-Cayley graphs
• Which Haar graphs are Cayley graphs?

This page was built for publication: Perfect codes of bi-Cayley graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6885387)