Аннотация:
Подмножество вершин $T$ графа $G$ является $k$-тестовым фрагментом, если сужения двух различных совершенных раскрасок графа $G$ в $k$ цветов на множество $T$ всегда различны. Длиной $k$-тестового фрагмента назовём его мощность. Объектами данного исследования являются $k$-тестовые фрагменты бесконечных циркулянтных графов. Бесконечный циркулянтный граф с дистанциями $d_1$, $d_2$, ..., $d_n$ — это граф, множество вершин которого совпадает с множеством целых чисел, а рёбрами соединены вершины, находящиеся на расстоянии $d_1$, $d_2$, ..., $d_n$ друг от друга. Если $d_i = i$ для всех $i$ от $1$ до $n$, то граф называется бесконечным циркулянтным графом со сплошным набором дистанций. В работе получены верхние оценки на длину $k$-тестовых фрагментов бесконечных циркулянтных графов со сплошным набором дистанций для всех $n$ и $k$. Более грубая оценка получена и для общего случая — бесконечных циркулянтных графов с дистанциями $d_1$, $d_2$, ..., $d_n$ и произвольного конечного $k$. (Совместная работа с С. В. Августиновичем.)
|
