Characterization and construction of total perfect codes in Semi-Cayley graphs

Articles in Press

Document Type : Original paper

Authors

1 Department of Mathematics, Faculty of Mathematical Sciences, University of Mazandaran, Babolsar, Iran

2 Department of Mathematics, Urmia University, P. O. Box 575615-1818, Urmia, Iran

Abstract

In this paper, we investigate the existence and construction of total perfect codes in semi-Cayley graphs. We first establish two equivalent characterizations for their existence: one in terms of a suitable vertex partition and the other through the defining subsets of the graph. These characterizations provide structural criteria for analyzing and constructing such codes. Furthermore, for a vertex subset $T=M_0\cup N_1$, we consider its adjugation, defined by $T^*=M_1\cup N_0$, and prove a necessary and sufficient condition for this operation to preserve the total perfect code property. As an application, we identify a distinguished family of total perfect codes generated from a vertex subset $T$ that is itself a total perfect code. Finally, we unify and extend several previously known results and characterize the relationship between the existence of total perfect codes in semi-Cayley graphs and the property that the graph is a pseudocover of a complete graph.

Keywords

Main Subjects

References

1] G. Abay-Asmerom, R.H. Hammack, and D.T. Taylor, Total perfect codes in tensor products of graphs, Ars Combin. 88 (2008), 129–134.
[2] N. Ahanjideh, Z. Akhlaghi, and B.G. Rodrigues, On perfect codes and total perfect codes in Cayley sum graph, J. Algebraic Combin. 63 (2026), no. 4, Article number: 52. https://doi.org/10.1007/s10801-026-01523-w
[3] N. Biggs, Perfect codes in graphs, J. Combin. Theory Ser. B 15 (1973), no. 3, 288–296.
https://doi.org/10.1016/0095-8956(73)90042-7
[4] J. Chen, Y. Wang, and B. Xia, Characterization of subgroup perfect codes in Cayley graphs, Discrete Math. 343 (2020), no. 5, 111813. https://doi.org/10.1016/j.disc.2020.111813
5] I.J. Dejter, Perfect domination in regular grid graphs, Australas. J. Combin. 42 (2008), 99–114.
[6] I.J. Dejter and O. Serra, Efficient dominating sets in Cayley graphs, Discrete Appl. Math. 129 (2003), no. 2-3, 319–328.
https://doi.org/10.1016/S0166-218X(02)00573-5
[7] M. Knor and P. Potoˇcnik, Efficient domination in cubic vertex-transitive graphs, European J. Combin. 33 (2012), no. 8, 1755–1764. https://doi.org/10.1016/j.ejc.2012.04.007
[8] M. Koohestani, D.A. Mojdeh, M. Ghasemi, and H. Khodaiemehr, On perfect codes in Cayley sum graphs, AKCE Int. J. Graphs Comb. (2026), In press.
[9] J. Lee, Independent perfect domination sets in Cayley graphs, J. Graph Theory 37 (2001), no. 4, 213–219.
https://doi.org/10.1002/jgt.1016
[10] X. Wang, L. Wei, S.J. Xu, and S. Zhou, Subgroup total perfect codes in Cayley sum graphs, Des. Codes Cryptogr. 92 (2024), no. 9, 2599–2613. https://doi.org/10.1007/s10623-024-01405-x
[11] X. Wang, S.J. Xu, and X. Li, Independent perfect dominating sets in semi-Cayley graphs, Theoret. Comput. Sci. 864 (2021), 50–57. https://doi.org/10.1016/j.tcs.2021.02.006
[12] Y. Wang, K. Yuan, and J.X. Li, Perfect codes of bi-Cayley graphs, J. Combin. Theory Ser. A 217 (2026), 106079. https://doi.org/10.1016/j.jcta.2025.106079
[13] J. Zhang, On subgroup perfect codes in Cayley sum graphs, Finite Fields Appl. 95 (2024), 102393. https://doi.org/10.1016/j.ffa.2024.102393
[14] J.X. Zhou and Y.Q. Feng, The automorphisms of bi-Cayley graphs, J. Combin.Theory Ser. B 116 (2016), 504–532.
http://dx.doi.org/10.1016/j.jctb.2015.10.004
[15] S. Zhou, Total perfect codes in Cayley graphs, Des. Codes Cryptogr. 81 (2016), no. 3, 489–504. https://doi.org/10.1007/s10623-015-0169-0
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 26 July 2026

Files

Share

How to cite

Statistics