Volume 19, No 4, 2012, P. 60-65

UDC 519.174
K. V. Vorob’ev 
Perfect multiple coverings of hypercube

Abstract:
A subset C of graph vertices is called a perfect k-multiple covering with a radius r if every vertex of this graph is within distance r from exactly k vertices of C. We give a criterion based on parameters of a perfect coloring. This criterion determines whether the perfect coloring is a perfect multiple covering with fixed radius r ≥ 1 of some multiplicity.
Bibliogr. 13.

Keywords: hypercube, perfect coloring, perfect code, perfect multiple coverings.

Vorob’ev Konstantin Vasil’evich ¹
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
e-mail: konstantin.vorobev@gmail.com