|
|
2023-ary quasigroups and related topics
August 19, 2022 11:00–12:30, Novosibirsk, Sobolev Institute of Mathematics, room 115
|
|
|
|
|
|
On test fragments of circulant graphs
M. A. Lisitsyna |
Number of views: |
This page: | 103 |
|
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
|
|