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, (), (London Math. Society Lecture Notes, No. 6)
[2] Biggs, N.L, (), (Cambridge Math. Tracts, No. 67)
[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, (), 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)
[7] van Lint, J.H, (), (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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.