Test fragments of perfect colorings of circulant graphs

Abstract

Let G=(V,E) be a transitive graph. A subset T of the vertex set V(G) is a k-test fragment if for every perfect k-coloring f of the graph G there exists a position of this fragment, whose partial coloring allows to reconstruct the whole f.

The objects of this study are k-test fragments of infinite circulant graphs. An infinite circulant graph with distances d₁ < d₂ < ... < d_n  is a graph, whose set of vertices is the set of integers, and two vertices are adjacent if they are on the distance d₁ , d₂ , ... or d_n. If d_i = i for all i from 1 to n, then the graph is called an infinite circulant graph with a continuous set of distances.

Upper bounds for the cardinalities of minimal k-test fragments of infinite circulant graphs with a continuous set of distances are obtained for any n and k. A rough estimate is also obtained in the general case - for infinite circulant graphs with distances d₁ , d₂ , ... , d_n and an arbitrary finite k.