Дискретная математика и математическая кибернетика
Тестовые фрагменты совершенных раскрасок циркулянтных графов
М. А. Лисицынаa,
С. В. Августиновичb 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
Аннотация:
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$.
Ключевые слова:
perfect coloring, infinite circulant graph,
$k$-test fragment.
УДК:
519.174.7
MSC: 05C50 Поступила 5 января 2023 г., опубликована
22 сентября 2023 г.
DOI:
10.33048/semi.2023.20.038