О спектрах категоричности для локально конечных графов

Исследуется алгоритмическая сложность изоморфизмов между вычислимыми копиями для локально конечных графов $G$ (неориентированных графов, в которых степень каждой вершины конечна). Получены следующие результаты. Если $G$ имеет конечное число компонент связности, то $G$ $\mathbf{d}$-вычислимо категоричный для любой тьюринговой степени $\mathbf{d}$ из класса $PA(\mathbf{0}')$. Если $G$ имеет бесконечно много компонент связности, то $G$ $\mathbf{0}''$-вычислимо категоричный. Строится серия примеров, устанавливающая оптимальность полученных оценок.