×

On the regularity of perfect 2-colorings of the Johnson graph. (English. Russian original) Zbl 1143.05031

Probl. Inf. Transm. 43, No. 4, 303-309 (2007); translation from Probl. Peredachi Inf. 43, No. 4, 37-44 (2007).
Summary: We study perfect colorings of the Johnson graph in two colors. We give sufficient conditions for a perfect coloring of the Johnson graph to be \(k\)-regular and present examples of perfect colorings. The proof of the theorem is in many respects similar to the proof of the result by Etzion and Schwartz [IEEE Trans. Inf. Theory 50, No. 9, 2156–2165 (2004)] on \(k\)-regularity of perfect codes.

MSC:

05C15 Coloring of graphs and hypergraphs
94B25 Combinatorial codes
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Etzion, T. and Schwartz, M., Perfect Constant-Weight Codes, IEEE Trans. Inform. Theory, 2004, vol. 50, no. 9, pp. 2156–2165. · Zbl 1298.94150 · doi:10.1109/TIT.2004.833355
[2] Fon-der-Flaass, D.G., Perfect Colorings of a Hypercube, in Proc. 985th AMS Meeting, Indiana Univ., Bloomington, USA, 2003, p. 31–32. · Zbl 1164.05348
[3] Zinoviev, V.A. and Rifà, J., On New Completely Regular q-ary Codes, Probl. Peredachi Inf., 2007, vol. 43, no. 2, pp. 34–51 [Probl. Inf. Trans. (Engl. Transl.), 2007, vol. 43, no. 2, pp. 97–112].
[4] Martin, W.J., Completely Regular Designs, J. Combin. Des., 1998, vol. 6, no. 4, pp. 261–273. · Zbl 04545838 · doi:10.1002/(SICI)1520-6610(1998)6:4<261::AID-JCD4>3.0.CO;2-D
[5] Delsarte, P., An Algebraic Approach to the Association Schemes of Coding Theory, Philips Res. Rep. Suppl., 1973, no. 10. · Zbl 1075.05606
[6] Ahlswede, R., Aydinian, H.K., and Khachatrian, L.H., On Perfect Codes and Related Concepts, Des. Codes Cryptogr., 2001, vol. 22, no. 3, pp. 221–237. · Zbl 0971.94014 · doi:10.1023/A:1008394205999
[7] Gordon, D.M., Perfect Single Error-Correcting Codes in the Johnson Scheme, IEEE Trans. Inform. Theory, 2006, vol. 52, no. 10, pp. 4670–4672. · Zbl 1323.94170 · doi:10.1109/TIT.2006.881744
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.