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.