Abstract:
A subset of vertices $T$ of a graph $G$ is a $k$-test fragment if the restrictions of two different perfect colorings of the graph $G$ in $k$ colors to the set $T$ are always distinct. The length of a $k$-test fragment is its cardinality. The objects of this study are $k$-test fragments of infinite circulant graphs. An infinite circulant graph with distances $d_1$, $d_2$, ..., $d_n$ is a graph whose set of vertices coincides with the set of integers, and edges connect vertices that are at distances $d_1$, $d_2$ , ..., $d_n$ from each other. 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. We obtain upper bounds on the length of $k$-test fragments of infinite circulant graphs with a continuous set of distances for all $n$ and $k$. A rougher estimate was also obtained for the general case — infinite circulant graphs with distances $d_1$, $d_2$, ..., $d_n$ and an arbitrary finite $k$. This is a joint work with S. V. Avgustinovich
|
