|
Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports], 2023, Volume 20, Issue 2, Pages 638–645 DOI: https://doi.org/10.33048/semi.2023.20.038
(Mi semr1601)
|
|
|
|
This article is cited in 1 scientific paper (total 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
DOI:
https://doi.org/10.33048/semi.2023.20.038
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.
Received January 5, 2023, published September 22, 2023
Citation:
M. A. Lisitsyna, S. V. Avgustinovich, “Test fragments of perfect colorings of circulant graphs”, Sib. Èlektron. Mat. Izv., 20:2 (2023), 638–645
Linking options:
https://www.mathnet.ru/eng/semr1601 https://www.mathnet.ru/eng/semr/v20/i2/p638
|
|