Interleaving schemes on circulant graphs with two offsets

Interleaving is used for error-correcting on a bursty noisy channel. Given a graph GG describing the topology of the channel, we label the vertices of GG so that each label-set is sufficiently sparse. The interleaving scheme corrects for any error burst of size at most tt; it is a labeling where the distance between any two vertices in the same label-set is at least tt.We consider interleaving schemes on infinite circulant graphs with two offsets 1 and dd. In such a graph the vertices are integers; edge ijij exists if and only if |i−j|∈{1,d}|i−j|∈{1,d}. Our goal is to minimize the number of labels used.Our constructions are covers of the graph by the minimal number of translates of some label-set SS. We focus on minimizing the index   of SS, which is the inverse of its density rounded up. We establish lower bounds and prove that our constructions are optimal or almost optimal, both for the index of SS and for the number of labels.