|
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.
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
|
Statistics & downloads: |
Abstract page: | 52 | Full-text PDF : | 11 | References: | 16 |
|