Characterizing subgroup perfect codes by 2-subgroups. (English) Zbl 1520.05050
Summary: A perfect code in a graph \(\Gamma\) is a subset \(C\) of \(V(\Gamma )\) such that no two vertices in \(C\) are adjacent and every vertex in \(V(\Gamma ){\setminus } C\) is adjacent to exactly one vertex in \(C\). Let \(G\) be a finite group and \(C\) a subset of \(G\). Then \(C\) is said to be a perfect code of \(G\) if there exists a Cayley graph of \(G\) admiting \(C\) as a perfect code. It is proved that a subgroup \(H\) of \(G\) is a perfect code of \(G\) if and only if a Sylow 2-subgroup of \(H\) is a perfect code of \(G\). This result provides a way to simplify the study of subgroup perfect codes of general groups to the study of subgroup perfect codes of 2-groups. As an application, a criterion for determining subgroup perfect codes of projective special linear groups \(\mathrm{PSL}(2,q)\) is given.
MSC:
| 05C25 | Graphs and abstract algebra (groups, rings, fields, etc.) |
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
| 94B25 | Combinatorial codes |
| 94B60 | Other types of codes |
References:
| [1] | Biggs, NL, Perfect codes in graphs, J. Comb. Theory Ser. B, 15, 289-296 (1973) · Zbl 0256.94009 · doi:10.1016/0095-8956(73)90042-7 |
| [2] | Brouwer, AE; Cohen, AM; Neumaier, A., Distance-regular Graphs (1989), Berlin: Springer, Berlin · Zbl 0747.05073 · doi:10.1007/978-3-642-74341-2 |
| [3] | Chen, J.; Wang, Y.; Xia, B., Characterization of subgroup perfect codes in Cayley graphs, Discret. Math., 343 (2020) · Zbl 1439.05104 · doi:10.1016/j.disc.2020.111813 |
| [4] | Chihara, L., On the zeros of the Askey-Wilson polynomials, with applications to coding theory, SIAM J. Math. Anal., 18, 1, 191-207 (1987) · Zbl 0611.33013 · doi:10.1137/0518015 |
| [5] | Dejter, IJ; Serra, O., Efficient dominating sets in Cayley graphs, Discret. Appl. Math., 129, 319-328 (2003) · Zbl 1035.05060 · doi:10.1016/S0166-218X(02)00573-5 |
| [6] | Delsarte, P., An algebraic approach to the association schemes of coding theory, Philips Res. Rep. Suppl., 10, 97 (1973) · Zbl 1075.05606 |
| [7] | Deng, Y-P; Sun, Y-Q; Liu, Q.; Wang, H-C, Efficient dominating sets in circulant graphs, Discret. Math., 340, 1503-1507 (2017) · Zbl 1361.05094 · doi:10.1016/j.disc.2017.02.014 |
| [8] | Dickson, LE, Linear Groups with an Exposition of the Galois Field Theory (1958), New York: Dover Publications Inc., New York · Zbl 0082.24901 |
| [9] | Feng, R.; Huang, H.; Zhou, S., Perfect codes in circulant graphs, Discret. Math., 340, 1522-1527 (2017) · Zbl 1361.05129 · doi:10.1016/j.disc.2017.02.007 |
| [10] | Golomb, SW; Welch, LR, Perfect codes in the Lee metric and the packing of polyominoes, SIAM J. Appl. Math., 18, 302-317 (1970) · Zbl 0192.56302 · doi:10.1137/0118025 |
| [11] | Hammond, P.; Smith, DH, Perfect codes in the graphs \(O_k\), J. Comb. Theory Ser. B, 19, 239-255 (1975) · Zbl 0282.94007 · doi:10.1016/0095-8956(75)90087-8 |
| [12] | Horak, P.; Kim, D., 50 years of the Golomb-Welch conjecture, IEEE Trans. Inform. Theory, 64, 3048-3061 (2018) · Zbl 1392.94928 · doi:10.1109/TIT.2017.2786675 |
| [13] | Huang, H.; Xia, B.; Zhou, S., Perfect codes in Cayley graphs, SIAM J. Discret. Math., 32, 548-559 (2018) · Zbl 1381.05032 · doi:10.1137/17M1129532 |
| [14] | Khaefi, Y.; Akhlaghi, Z.; Khosravi, B., On the subgroup perfect codes in Cayley graphs, Des. Codes Cryptogr., 91, 55-61 (2023) · Zbl 1506.05090 · doi:10.1007/s10623-022-01098-0 |
| [15] | Kratochvíl, J., Perfect codes over graphs, J. Comb. Theory Ser. B, 40, 224-228 (1986) · Zbl 0563.94017 · doi:10.1016/0095-8956(86)90079-1 |
| [16] | Krotov, DS, The existence of perfect codes in Doob graphs, IEEE Trans. Inf. Theory, 66, 3, 1423-1427 (2020) · Zbl 1446.94184 · doi:10.1109/TIT.2019.2946612 |
| [17] | Kurzweil, H.; Stellmacher, B., The Theory of Finite Groups: An Introduction (2004), New York: Springer, New York · Zbl 1047.20011 · doi:10.1007/b97433 |
| [18] | Lee, J., Independent perfect domination sets in Cayley graphs, J. Graph Theory, 37, 213-219 (2001) · Zbl 0996.05096 · doi:10.1002/jgt.1016 |
| [19] | Leung, KH; Zhou, Y., No lattice tiling of \(\mathbb{Z}_n\) by Lee sphere of radius \(2\), J. Comb. Theory Ser. A, 171 (2020) · Zbl 1433.05148 · doi:10.1016/j.jcta.2019.105157 |
| [20] | Lloyd, SP, Binary block coding, Bell Syst. Tech. J., 36, 517-535 (1957) · doi:10.1002/j.1538-7305.1957.tb02410.x |
| [21] | Ma, X.; Walls, GL; Wang, K.; Zhou, S., Subgroup perfect codes in Cayley graphs, SIAM J. Discret. Math., 34, 1909-1921 (2020) · Zbl 1453.05045 · doi:10.1137/19M1258013 |
| [22] | MacWilliams, FJ; Sloane, NJA, The Theory of Error-Correcting Codes (1977), Amsterdam: North-Holland, Amsterdam · Zbl 0369.94008 |
| [23] | Martin, WJ; Zhu, XJ, Anticodes for the Grassman and bilinear forms graphs, Des. Codes Cryptogr., 6, 1, 73-79 (1995) · Zbl 0852.94021 · doi:10.1007/BF01390772 |
| [24] | Schwartz, M.; Etzion, T., Codes and anticodes in the Grassman graph, J. Comb. Theory Ser. A, 97, 27-42 (2002) · Zbl 1006.94028 · doi:10.1006/jcta.2001.3188 |
| [25] | Shi, M.; Huang, D.; Krotov, DS, Additive perfect codes in Doob graphs, Des. Codes Cryptogr., 87, 8, 1857-1869 (2019) · Zbl 1409.94927 · doi:10.1007/s10623-018-0586-y |
| [26] | Suzuki, M., Group Theory I (1982), New York: Springer, New York · Zbl 0472.20001 · doi:10.1007/978-3-642-61804-8 |
| [27] | Tamizh, CT; Mutharasu, S., Subgroups as efficient dominating sets in Cayley graphs, Discret. Appl. Math., 161, 1187-1190 (2013) · Zbl 1277.05130 · doi:10.1016/j.dam.2012.09.005 |
| [28] | Thas, JA, Polar spaces, generalized hexagons and perfect codes, J. Comb. Theory Ser. A, 29, 87-93 (1980) · Zbl 0444.05027 · doi:10.1016/0097-3165(80)90049-7 |
| [29] | Tietäväinen, A., On the nonexistence of perfect codes over finite fields, SIAM J. Appl. Math., 24, 88-96 (1973) · doi:10.1137/0124010 |
| [30] | van Lint J. H.: Nonexistence theorems for perfect error-correcting codes. In: Computers in Algebra and Number Theory, vol. IV, SIAM-AMS Proceedings (1971). · Zbl 0243.94007 |
| [31] | van Lint, JH, A survey of perfect codes, Rocky Mt. J. Math., 5, 199-224 (1975) · Zbl 0301.94007 · doi:10.1216/RMJ-1975-5-2-199 |
| [32] | Zhang, J.; Zhou, S., On subgroup perfect codes in Cayley graphs, Eur. J. Comb., 91 (2021) · Zbl 1459.05126 · doi:10.1016/j.ejc.2020.103228 |
| [33] | Zhang, J.; Zhou, S., Corrigendum to “On subgroup perfect codes in Cayley graphs [Eur. J. Comb. 91, 103228 (2022)]”, Eur. J. Comb., 101, 103461 (2022) · Zbl 1477.05089 · doi:10.1016/j.ejc.2021.103461 |
| [34] | Zhou, S., Total perfect codes in Cayley graphs, Des. Codes Cryptogr., 81, 489-504 (2016) · Zbl 1347.05097 · doi:10.1007/s10623-015-0169-0 |
| [35] | Zhou, S., Cyclotomic graphs and perfect codes, J. Pure Appl. Algebra, 223, 931-947 (2019) · Zbl 1400.05117 · doi:10.1016/j.jpaa.2018.05.007 |
| [36] | Zinoviev, VA; Leontiev, VK, The nonexistence of perfect codes over Galois fields, Probl. Control Inf. Theory, 2, 123-132 (1973) · Zbl 0318.94013 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
