Entry-faithful 2-neighbour transitive codes | Designs, Codes and Cryptography Skip to main content
Springer Nature Link
Log in

Entry-faithful 2-neighbour transitive codes

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

Abstract

We consider a code to be a subset of the vertex set of a Hamming graph. The set of \(s\)-neighbours of a code is the set of vertices, not in the code, at distance \(s\) from some codeword, but not distance less than \(s\) from any codeword. A \(2\)-neighbour transitive code is a code which admits a group \(X\) of automorphisms which is transitive on the \(s\)-neighbours, for \(s=1,2\), and transitive on the code itself. We give a classification of \(2\)-neighbour transitive codes, with minimum distance \(\delta \geqslant 5\), for which \(X\) acts faithfully on the set of entries of the Hamming graph.

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
¥17,985 /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 (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Best M.R., Brouwer A.E., Macwilliams F.J., Odlyzko A.M., Sloane N.J.A.: Bounds for binary codes of length less than 25. IEEE Trans. Inf. Theory 24, 81–93 (1978).

  2. Bochert A.: Ueber die zahl der verschiedenen werthe, die eine function gegebener buchstaben durch vertauschung derselben erlangen kann. Math. Ann. 33(4), 584–590 (1889).

  3. Borges J., Rifà J.: On the nonexistence of completely transitive codes. IEEE Trans. Inf. Theory 46(1), 279–280 (2000).

  4. Borges J., Rifà J.: On linear completely regular codes with covering radius \(\rho =1\). Construction and classification. CoRR http://www.abs/0906.0550, (2009).

  5. Borges J., Rifà J., Zinoviev V.A.: Nonexistence of completely transitive codes with error-correcting capability e > 3. IEEE Trans. Inf. Theory 47(4), 1619–1621 (2001).

  6. Borges J., Rifà J., Zinoviev V.A.: New families of completely transitive codes and distance transitive graphs. arXiv preprint arXiv:1304.2151 (2013).

  7. Borges J., Rifà J., Zinoviev V.A.: New families of completely regular codes and their corresponding distance regular coset graphs. Des. Codes Cryptogr. 70(1–2), 139–148 (2014).

  8. Borges J., Rifà J., Zinoviev V.A.: On \(q\)-ary linear completely regular codes with \(\rho = 2\) and antipodal dual. Adv. Math. Commun. (AMC) 4(4), 567–578 (2010).

  9. Brouwer A.E., Cohen A.M., Neumaier A.: Distance-Regular Graphs. Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], vol. 18. Springer, Berlin (1989).

  10. Cameron P.J.: Permutation Groups. London Mathematical Society Student Texts, vol. 45. Cambridge University Press, Cambridge (1999).

  11. Conway J.H.: Atlas of Finite Groups: Maximal Subgroups and Ordinary Characters for Simple Groups. Clarendon Press, Oxford (1985).

  12. Delsarte P.: An Algebraic Approach to the Association Schemes of Coding Theory. Philips Research Reports: Supplements. N. V. Philips’ Gloeilampenfabrieken (1973).

  13. Devillers A., Giudici M., Li C.H., Pearce G., Praeger C.E.: On imprimitive rank 3 permutation groups. J. Lond. Math. Soc. 84(3), 649–669 (2011).

  14. Dixon J.D., Mortimer B.: Permutation Groups. Graduate Texts in Mathematics, vol. 163. Springer, New York (1996).

  15. Gillespie, N.I.: Neighbour transitivity on codes in Hamming graphs. PhD thesis, The University of Western Australia, Perth, Australia (2011)

  16. Gillespie N.I., Praeger C.E.: Complete transitivity of the Nordstrom–Robinson codes. arXiv e-prints arXiv:1205.3878 (2012).

  17. Gillespie N.I., Praeger C.E.: Neighbour transitivity on codes in Hamming graphs. Des. Codes Cryptogr. 67(3), 385–393 (2013).

  18. Gillespie N.I., Praeger C.E.: Uniqueness of certain completely regular Hadamard codes. J. Comb. Theory A 120(7), 1394–1400 (2013).

  19. Gillespie N.I., Praeger C.E.: Characterisation of a family of neighbour transitive codes. arXiv e-prints arXiv:1405.5427 (2014).

  20. Gillespie N.I., Giudici M., Praeger C.E.: Classification of a family of completely transitive codes. arXiv preprint arXiv:1208.0393 (2012).

  21. Gillespie N.I., Praeger C.E.: Diagonally neighbour transitive codes and frequency permutation arrays. J. Algebr. Comb. 39(3), 733–747 (2014).

  22. Giudici M., Praeger C.E.: Completely transitive codes in Hamming graphs. Eur. J. Comb. 20(7), 647–662 (1999).

  23. Hall Jr. M.: Note on the Mathieu group \({M}_{12}\). Arch. Math. 13(1), 334–340 (1962).

  24. Kantor W.M.: k-Homogeneous groups. Math. Z. 124(4), 261–265 (1972).

  25. Liebeck M.W., Praeger C.E., Saxl J.: A classification of the maximal subgroups of the finite alternating and symmetric groups. J. Algebra 111(2), 365–383 (1987).

  26. MacWilliams F.J., Sloane N.J.A.: The Theory of Error Correcting Codes. North-Holland Mathematical Library. North-Holland, Amsterdam (1978).

  27. Neumaier A.: Completely regular codes. Discret. Math. 106–107, 353–360 (1992).

  28. Praeger C.E.: The inclusion problem for finite primitive permutation groups. Proc. Lond. Math. Soc. 3(1), 68–88 (1990).

  29. Solé P.: Completely regular codes and completely transitive codes. Discret. Math. 81(2), 193–201 (1990).

  30. Solé P.: Completely regular codes and completely transitive codes. RR-0727, (1987). \(\langle \)inria-00075825\(\rangle \).

  31. Stinson D.R.: Combinatorial Designs: Construction and Analysis. Springer, New York (2004).

  32. Todd J.A.: A combinatorial problem. J. Math. Phys. 12, 321–333 (1933).

  33. van Tilborg H.C.: Uniformly Packed Codes. Technische Hogeschool, Eindhoven (1976).

Download references

Acknowledgments

The research for this paper was supported by a Grant associated with Australian Research Council Federation Fellowship FF0776186. The third author is supported by an Australian Postgraduate Award and UWA Top-up Scholarship. We would like to acknowledge the careful and detailed comments of the referees, including a simplification in the proof of Proposition 4.3.

Author information

Authors and Affiliations

  1. Heilbronn Institute for Mathematical Research, School of Mathematics, Howard House, University of Bristol, Bristol, BS8 1SN, UK

    Neil I. Gillespie

  2. Centre for the Mathematics of Symmetry and Computation, University of Western Australia, 35 Stirling Highway, Crawley, WA, 6009, Australia

    Michael Giudici, Daniel R. Hawtin & Cheryl E. Praeger

Authors
  1. Neil I. Gillespie
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Michael Giudici
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Daniel R. Hawtin
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Cheryl E. Praeger
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Daniel R. Hawtin.

Additional information

This is one of several papers published in Designs, Codes and Cryptography comprising the “Special Issue on Finite Geometries”.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Gillespie, N.I., Giudici, M., Hawtin, D.R. et al. Entry-faithful 2-neighbour transitive codes. Des. Codes Cryptogr. 79, 549–564 (2016). https://doi.org/10.1007/s10623-015-0069-3

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10623-015-0069-3

Keywords

Mathematics Subject Classification

Search

Navigation