Perfect codes in graphs. (English) Zbl 0256.94009

Summary: The classical problem of the existence of perfect codes is set in a vector space. In this paper it is shown that the natural setting for the problem is the class of distance-transitive graphs. A general theory is developed that leads to a simple criterion for the existence of a perfect code in a distance-transitive graph, and it is shown that this criterion implies Lloyd’s theorem in the classical case.


94B60 Other types of codes
05C90 Applications of graph theory
Full Text: DOI


[1] Biggs, N. L., (Finite Groups of Automorphisms (1971), Cambridge Univ. Press: Cambridge Univ. Press London), (London Math. Society Lecture Notes, No. 6) · Zbl 0221.05049
[2] Biggs, N. L., (Algebraic Graph Theory (1974), Cambridge Univ. Press: Cambridge Univ. Press London), (Cambridge Math. Tracts, No. 67) · Zbl 0284.05101
[3] Biggs, N. L.; Smith, D. H., On trivalent graphs, Bull. London Math. Soc., 3, 155-158 (1971) · Zbl 0217.02404
[4] Golay, M. J.E, Notes on digital coding, (Proc. IRE, 37 (1949)), 657
[5] Lenstra, H. W., Two theorems on perfect codes, Discrete Math., 3, 125-132 (1972) · Zbl 0248.94017
[6] Tietäväinen, A., On the non-existence of perfect codes over finite fields, SIAM J. Appl. Math., 24, 88-96 (1973) · Zbl 0233.94004
[7] van Lint, J. H., (Coding Theory (1971), Springer-Verlag: Springer-Verlag New York/Berlin), (Lecture Notes in Math., No. 201) · Zbl 0972.01034
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.