Test fragments of perfect colorings of circulant graphs

M. A. Lisitsyna ; S. V. Avgustinovich

Sibirskie èlektronnye matematičeskie izvestiâ, Tome 20 (2023) no. 2, pp. 638-645

Résumé

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 $\phi$ of the graph $G$ there exists a position of this fragment, whose partial coloring allows to reconstruct the whole $\phi$. The objects of this study are $k$-test fragments of infinite circulant graphs. An infinite circulant graph with distances $d_1 d_2 \ldots d_n$ is a graph, whose set of vertices is the set of integers, and two vertices $i$ and $j$ are adjacent if $|i-j| \in \{d_1,d_2,…,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_1, d_2, \ldots , d_n$ and an arbitrary finite $k$.

Détail

Keywords: perfect coloring
Mots-clés : infinite circulant graph, $k$-test fragment.