Interleaving schemes on circulant graphs with two offsets

Interleaving is used for error-correcting on a bursty noisy channel. Given a graph G describing the topology of the channel, we label the vertices of G so that each label-set is sufficiently sparse. The interleaving scheme corrects for any error burst of size at most t ; it is a labeling where the distance between any two vertices in the same label-set is at least t . sider interleaving schemes on infinite circulant graphs with two offsets 1 and d . In such a graph the vertices are integers; edge i j exists if and only if | i − j | ∈ { 1 , d } . Our goal is to minimize the number of labels used. nstructions are covers of the graph by the minimal number of translates of some label-set S . We focus on minimizing the index of S , 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 S and for the number of labels.