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 ϕ 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.

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

Dates:

Submitted:	Jan 5, 2023
Published print:	Nov 7, 2023
Published online:	Nov 7, 2023

Identifiers:

Web of science:	WOS:001164414700001
Scopus:	2-s2.0-85176377773

Citing:

DB	Citing
Scopus	1
Web of science	1

Altmetrics: