Geodesic
On a metric property of perfect colorings
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 18 (2021) no. 1, pp. 640-646.

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

Given a perfect coloring of a graph, we prove that the $L_1$ distance between two rows of the adjacency matrix of the graph is not less than the $L_1$ distance between the corresponding rows of the parameter matrix of the coloring. With the help of an algebraic approach, we deduce corollaries of this result for perfect $2$-colorings and perfect colorings in distance-$l$ graphs and distance-regular graphs. We also provide examples of infinite graphs, where the obtained property rejects several putative parameter matrices of perfect colorings.
Keywords: perfect coloring, perfect structure, square grid, triangular grid.
Mots-clés : $L_1$ distance, circulant graph 
@article{SEMR_2021_18_1_a20,
     author = {A. A. Taranenko},
     title = {On a metric property of perfect colorings},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {640--646},
     publisher = {mathdoc},
     volume = {18},
     number = {1},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2021_18_1_a20/}
}
TY  - JOUR
AU  - A. A. Taranenko
TI  - On a metric property of perfect colorings
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2021
SP  - 640
EP  - 646
VL  - 18
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2021_18_1_a20/
LA  - en
ID  - SEMR_2021_18_1_a20
ER  - 
%0 Journal Article
%A A. A. Taranenko
%T On a metric property of perfect colorings
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2021
%P 640-646
%V 18
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2021_18_1_a20/
%G en
%F SEMR_2021_18_1_a20
A. A. Taranenko. On a metric property of perfect colorings. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 18 (2021) no. 1, pp. 640-646. http://geodesic.mathdoc.fr/item/SEMR_2021_18_1_a20/

[1] M.A. Axenovich, “On multiple coverings of the infinite rectangular grid with balls of constant radius”, Discrete Math., 268:1-3 (2003), 31–48 | DOI | MR | Zbl

[2] A.E. Brouwer, A.M. Cohen, A. Neumaier, Distance-regular graphs, Ergebnisse der Mathematik und ihrer Grenzgebiete, 3, no. 18, Springer-Verlag, Berlin etc., 1989 | MR | Zbl

[3] P. Delsarte, An algebraic approach to the association schemes of coding theory, Philips Research Reports. Supplements 10, Historical Jrl., Ann Arbor, 1973 | MR | Zbl

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

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

[6] S.A. Puzynina, “Perfect colorings of vertices of the graph $G(Z^2)$ in three colors”, Diskretn. Anal. Issled. Oper., Ser. 2, 12:1 (2005), 37–54 | MR | Zbl

[7] S.A. Puzynina, “On periodicity of perfect colorings of infinite hexagonal and triangular grids”, Sib. Math. J., 52:1 (2011), 91–104 | DOI | MR | Zbl

[8] A.A. Taranenko, “Algebraic properties of perfect structures”, Linear Algebra Appl., 607 (2020), 286–306 | DOI | MR | Zbl