[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Characterizing subgroup perfect codes by 2-subgroups

  • Published:
Designs, Codes and Cryptography Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Data Availability

No data, models, or code were generated or used during the study.

References

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Book  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Book  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MATH  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Book  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Google Scholar 

Download references

Acknowledgements

This work was supported by the Natural Science Foundation of Chongqing (CSTB2022NSCQ-MSX1054) and the Foundation of Chongqing Normal University (21XLB006).

Author information

Authors and Affiliations

  1. School of Mathematical Sciences, Chongqing Normal University, Chongqing, 401331, People’s Republic of China

    Junyang Zhang

Authors
  1. Junyang Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Junyang Zhang.

Additional information

Communicated by C. J. Colbourn.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Zhang, J. Characterizing subgroup perfect codes by 2-subgroups. Des. Codes Cryptogr. 91, 2811–2819 (2023). https://doi.org/10.1007/s10623-023-01240-6

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10623-023-01240-6

Keywords

Mathematics Subject Classification

Search

Navigation