Реферат: 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 ϕ of the graph G there exists a position of this fragment, whose partial coloring allows to reconstruct the whole ϕ. The objects of this study are k-test fragments of innite circulant graphs. An innite circulant graph with distances d1 < d2 < ... < dn is a graph, whose set of vertices is the set of integers, and two vertices i and j are adjacent if |i−j| ∈ {d1,d2,...,dn}. If di = i for all i from 1 to n, then the graph is called an in nite circulant graph with a continuous set of distances. Upper bounds for the cardinalities of minimal k-test fragments of innite 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 innite circulant graphs with distances d1,d2,...,dn and an arbitrary nite k.

Библиографическая ссылка: Лисицына М.А. , Августинович С.В.
Тестовые фрагменты совершенных раскрасок циркулянтных графов
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports). 2023. Т.20. №2. С.638-645. DOI: 10.33048/semi.2023.20.038 WOS Scopus РИНЦ

Даты:

Поступила в редакцию:	5 янв. 2023 г.
Опубликована в печати:	7 нояб. 2023 г.
Опубликована online:	7 нояб. 2023 г.

Идентификаторы БД:

Web of science:	WOS:001164414700001
Scopus:	2-s2.0-85176377773
РИНЦ:	82134626

Цитирование в БД:

БД	Цитирований
Scopus	1
Web of science	1

Альметрики: