Тестовые фрагменты совершенных раскрасок циркулянтных графов

Аннотация

Пусть G=(V,E) - произвольный транзитивный граф. Подмножество T множества вершин V(G) является k-тестовым фрагментом, если для любой совершенной k-раскраски f графа G, найдется такое положение этого фрагмента, частичная раскраска которого позволяет восстановить всю f.

Объектами исследования являются k-тестовые фрагменты бесконечных циркулянтных графов. Бесконечный циркулянтный граф с дистанциями d₁ < d₂ < ... < d_n - это граф, множество вершин которого совпадает с множеством целых чисел, а рёбрами соединены вершины, находящиеся на расстоянии d₁ , d₂ , ... или d_n. Если d_i = i для всех i от 1 до n, тогда граф назовем бесконечным циркулянтным графом со сплошным набором дистанций.

В работе получены верхние оценки на длины минимальных k-тестовых фрагментов бесконечных циркулянтных графов со сплошным набором дистанций для произвольных натуральных k и n. Грубая оценка получена также и в общем случае - для бесконечного циркулянтного графа с дистанциями d₁ , d₂ , ... , d_n и произвольного конечного k.