Top

Designs, Codes and Cryptography

Published in:

16-05-2023

Characterizing subgroup perfect codes by 2-subgroups

Author: Junyang Zhang

Published in: Designs, Codes and Cryptography | Issue 9/2023

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

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 \(\textrm{PSL}(2,q)\) is given.

previous article Obituary of Professor Zhexian Wan

next article Several families of irreducible constacyclic and cyclic codes

Biggs N.L.: Perfect codes in graphs. J. Comb. Theory Ser. B 15, 289–296 (1973).MathSciNetCrossRefMATH

Brouwer A.E., Cohen A.M., Neumaier A.: Distance-regular Graphs. Springer, Berlin (1989).CrossRefMATH

Chen J., Wang Y., Xia B.: Characterization of subgroup perfect codes in Cayley graphs. Discret. Math. 343, 111813 (2020).MathSciNetCrossRefMATH

Chihara L.: On the zeros of the Askey–Wilson polynomials, with applications to coding theory. SIAM J. Math. Anal. 18(1), 191–207 (1987).MathSciNetCrossRefMATH

Dejter I.J., Serra O.: Efficient dominating sets in Cayley graphs. Discret. Appl. Math. 129, 319–328 (2003).MathSciNetCrossRefMATH

Delsarte P.: An algebraic approach to the association schemes of coding theory. Philips Res. Rep. Suppl. 10, 97 (1973).MathSciNetMATH

Deng Y.-P., Sun Y.-Q., Liu Q., Wang H.-C.: Efficient dominating sets in circulant graphs. Discret. Math. 340, 1503–1507 (2017).MathSciNetCrossRefMATH

Dickson L.E.: Linear Groups with an Exposition of the Galois Field Theory. Dover Publications Inc., New York (1958).MATH

Feng R., Huang H., Zhou S.: Perfect codes in circulant graphs. Discret. Math. 340, 1522–1527 (2017).MathSciNetCrossRefMATH

10.

Golomb S.W., Welch L.R.: Perfect codes in the Lee metric and the packing of polyominoes. SIAM J. Appl. Math. 18, 302–317 (1970).MathSciNetCrossRefMATH

11.

Hammond P., Smith D.H.: Perfect codes in the graphs \(O_{k}\). J. Comb. Theory Ser. B 19, 239–255 (1975).CrossRefMATH

12.

Horak P., Kim D.: 50 years of the Golomb–Welch conjecture. IEEE Trans. Inform. Theory 64, 3048–3061 (2018).MathSciNetCrossRefMATH

13.

Huang H., Xia B., Zhou S.: Perfect codes in Cayley graphs. SIAM J. Discret. Math. 32, 548–559 (2018).MathSciNetCrossRefMATH

14.

Khaefi Y., Akhlaghi Z., Khosravi B.: On the subgroup perfect codes in Cayley graphs. Des. Codes Cryptogr. 91, 55–61 (2023).MathSciNetCrossRefMATH

15.

Kratochvíl J.: Perfect codes over graphs. J. Comb. Theory Ser. B 40, 224–228 (1986).MathSciNetCrossRefMATH

16.

Krotov D.S.: The existence of perfect codes in Doob graphs. IEEE Trans. Inf. Theory 66(3), 1423–1427 (2020).MathSciNetCrossRefMATH

17.

Kurzweil H., Stellmacher B.: The Theory of Finite Groups: An Introduction. Universitext. Springer, New York (2004).CrossRefMATH

18.

Lee J.: Independent perfect domination sets in Cayley graphs. J. Graph Theory 37, 213–219 (2001).MathSciNetCrossRefMATH

19.

Leung K.H., Zhou Y.: No lattice tiling of \(\mathbb{Z} _{n}\) by Lee sphere of radius \(2\). J. Comb. Theory Ser. A 171, 105157 (2020).CrossRefMATH

20.

Lloyd S.P.: Binary block coding. Bell Syst. Tech. J. 36, 517–535 (1957).MathSciNetCrossRef

21.

Ma X., Walls G.L., Wang K., Zhou S.: Subgroup perfect codes in Cayley graphs. SIAM J. Discret. Math. 34, 1909–1921 (2020).MathSciNetCrossRefMATH

22.

MacWilliams F.J., Sloane N.J.A.: The Theory of Error-Correcting Codes. North-Holland, Amsterdam (1977).MATH

23.

Martin W.J., Zhu X.J.: Anticodes for the Grassman and bilinear forms graphs. Des. Codes Cryptogr. 6(1), 73–79 (1995).MathSciNetCrossRefMATH

24.

Schwartz M., Etzion T.: Codes and anticodes in the Grassman graph. J. Comb. Theory Ser. A 97, 27–42 (2002).MathSciNetCrossRefMATH

25.

Shi M., Huang D., Krotov D.S.: Additive perfect codes in Doob graphs. Des. Codes Cryptogr. 87(8), 1857–1869 (2019).MathSciNetCrossRefMATH

26.

Suzuki M.: Group Theory I. Springer, New York (1982).CrossRefMATH

27.

Tamizh C.T., Mutharasu S.: Subgroups as efficient dominating sets in Cayley graphs. Discret. Appl. Math. 161, 1187–1190 (2013).MathSciNetCrossRefMATH

28.

Thas J.A.: Polar spaces, generalized hexagons and perfect codes. J. Comb. Theory Ser. A 29, 87–93 (1980).MathSciNetCrossRefMATH

29.

Tietäväinen A.: On the nonexistence of perfect codes over finite fields. SIAM J. Appl. Math. 24, 88–96 (1973).MathSciNetCrossRef

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).

31.

van Lint J.H.: A survey of perfect codes. Rocky Mt. J. Math. 5, 199–224 (1975).MathSciNetCrossRefMATH

32.

Zhang J., Zhou S.: On subgroup perfect codes in Cayley graphs. Eur. J. Comb. 91, 103228 (2021).MathSciNetCrossRefMATH

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).CrossRefMATH

34.

Zhou S.: Total perfect codes in Cayley graphs. Des. Codes Cryptogr. 81, 489–504 (2016).MathSciNetCrossRefMATH

35.

Zhou S.: Cyclotomic graphs and perfect codes. J. Pure Appl. Algebra 223, 931–947 (2019).MathSciNetCrossRefMATH

36.

Zinoviev V.A., Leontiev V.K.: The nonexistence of perfect codes over Galois fields. Probl. Control Inf. Theory 2, 123–132 (1973).

Title: Characterizing subgroup perfect codes by 2-subgroups
Author: Junyang Zhang
Publication date: 16-05-2023
Publisher: Springer US
Published in: Designs, Codes and Cryptography / Issue 9/2023
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-023-01240-6

Springer Professional

Characterizing subgroup perfect codes by 2-subgroups

Abstract

Premium Partner

Springer Professional

Abstract

Please log in to get access to your license.

Other articles of this Issue 9/2023

The proportion of non-degenerate complementary subspaces in classical spaces

Meet-in-the-middle attack with splice-and-cut technique and a general automatic framework

Obituary of Professor Zhexian Wan

Several families of irreducible constacyclic and cyclic codes

On the algebraic immunity—resiliency trade-off, implications for Goldreich’s pseudorandom generator

Hiding the input-size in multi-party private set intersection

Premium Partner