RUS  ENG
Full version
JOURNALS // Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports] // Archive

Sib. Èlektron. Mat. Izv., 2023 Volume 20, Issue 2, Pages 638–645 (Mi semr1601)

This article is cited in 1 paper

Discrete mathematics and mathematical cybernetics

Test fragments of perfect colorings of circulant graphs

M. A. Lisitsynaa, S. V. Avgustinovichb

a Budyonny Military Academy of the Signal Corps, pr. Tikhoretsky, 3, 194064, St Petersburg, Russia
b Sobolev Institute of Mathematics, pr. Koptyuga, 4, 630090, Novosibirsk, Russia

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 $\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$.

Keywords: perfect coloring, infinite circulant graph, $k$-test fragment.

UDC: 519.174.7

MSC: 05C50

Received January 5, 2023, published September 22, 2023

DOI: 10.33048/semi.2023.20.038



© Steklov Math. Inst. of RAS, 2025