On Categoricity Spectra for Locally Finite Graphs

Under study is the algorithmic complexity of isomorphisms between computable copies of locally finite graphs $ G $ (undirected graphs whose every vertex has finite degree). We obtain the following results: If $ G $ has only finitely many components then $ G $ is $ {\mathbf{d}} $ -computably categorical for every Turing degree $ {\mathbf{d}} $ from the class $ PA({\mathbf{0}}^{\prime}) $ . If $ G $ has infinitely many components then $ G $ is $ {\mathbf{0}}^{\prime\prime} $ -computably categorical. We exhibit a series of examples showing that the obtained bounds are sharp.