Geodesic
Test fragments of perfect colorings of circulant graphs
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 20 (2023) no. 2, pp. 638-645.

Voir la notice de l'article provenant de la source Math-Net.Ru

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
Mots-clés : infinite circulant graph, $k$-test fragment. 
@article{SEMR_2023_20_2_a33,
     author = {M. A. Lisitsyna and S. V. Avgustinovich},
     title = {Test fragments of perfect colorings of circulant graphs},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {638--645},
     publisher = {mathdoc},
     volume = {20},
     number = {2},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2023_20_2_a33/}
}
TY  - JOUR
AU  - M. A. Lisitsyna
AU  - S. V. Avgustinovich
TI  - Test fragments of perfect colorings of circulant graphs
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2023
SP  - 638
EP  - 645
VL  - 20
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2023_20_2_a33/
LA  - ru
ID  - SEMR_2023_20_2_a33
ER  - 
%0 Journal Article
%A M. A. Lisitsyna
%A S. V. Avgustinovich
%T Test fragments of perfect colorings of circulant graphs
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2023
%P 638-645
%V 20
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2023_20_2_a33/
%G ru
%F SEMR_2023_20_2_a33
M. A. Lisitsyna; S. V. Avgustinovich. Test fragments of perfect colorings of circulant graphs. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 20 (2023) no. 2, pp. 638-645. http://geodesic.mathdoc.fr/item/SEMR_2023_20_2_a33/

[1] S.V. Avgustinovich, “On a property of perfect binary codes”, Diskretn. Anal. Issled. Oper., 2:1 (1995), 4–6 | MR | Zbl

[2] S.V. Avgustinovich, A.Yu. Vasil'eva, “Computation of a centered function through its values on middle layers of the Boolean cube”, Diskretn. Anal. Issled. Oper., Ser. 1, 10:2 (2003), 3–16 | MR | Zbl

[3] A.Yu. Vasil'eva, “On reconstructive sets of vertices in the Boolean cube”, J. Appl. Ind. Math., 6:3 (2012), 393–402 | DOI | MR | Zbl

[4] D.B. Khoroshilova, “On the parameters of perfect 2-colorings of circulant graphs”, Diskretn. Anal. Issled. Oper., 18:6 (2011), 82–89 | MR | Zbl

[5] D.B. Khoroshilova, “On circular perfect two-color colorings”, Diskretn. Anal. Issled. Oper., 16:1 (2009), 80–92 | MR | Zbl

[6] O.G. Parshina, “Perfect 2-colorings of infinite circulant graphs with a continuous set of distances”, J. Appl. Industr. Math., 8:3 (2014), 357–361 | DOI | MR | Zbl

[7] O.G. Parshina, M.A. Lisitsyna, “The perfect 2-colorings of infinite circulant graphs with a continuous set of odd distances”, Sib. Èlectron. Math. Izv., 17 (2020), 590–603 | DOI | MR | Zbl

[8] M.A. Lisitsyna, S.V. Avgustinovich, “Perfect colorings of the prism graph”, Sib. Èlectron. Math. Izv., 13 (2016), 1116–1128 | MR | Zbl

[9] M.A. Lisitsyna, O.G. Parshina, “Perfect colorings of the infinite circulant graph with distances 1 and 2”, J. Appl. Industr. Math., 11:3 (2017), 381–388 | DOI | MR | Zbl

[10] V.D. Plaksina, P.A. Shcherbina, “New perfect colorings of infinite circulant graphs with continuous sets of distanses”, Sib. Èlectron. Math. Izv., 18:1 (2021), 530–533 | DOI | MR | Zbl

[11] V.G. Vizing, “The number of edges in a graph of given radius”, Sov. Math., Dokl., 8 (1967), 535–536 | MR | Zbl