ON CATEGORICITY SPECTRA FOR LOCALLY FINITE GRAPHS

被引：0

作者：

Bazhenov, N. A. ^{[1
]}

Marchuk, M., I ^{[1
]}

机构：

[1] Sobolev Inst Math, Novosibirsk, Russia

来源：

SIBERIAN MATHEMATICAL JOURNAL | 2021年 / 62卷 / 05期

基金：

俄罗斯基础研究基金会;

关键词：

computable categoricity; autostability; degree of categoricity; categoricity spectrum; computable model; locally finite graph;

D O I：

10.1134/S0037446621050037; 10.1134/S0081543811060071

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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 d-computably categorical for every Turing degree d from the class PA(0'). If G has infinitely many components then G is 0 ''-computably categorical. We exhibit a series of examples showing that the obtained bounds are sharp.

引用

页码：796 / 804

页数：9

共 50 条

[21] Approximately uniformly locally finite graphs
Manuilov, V
LINEAR ALGEBRA AND ITS APPLICATIONS, 2019, 569 : 146 - 155
[22] SOBOLEV SPACES ON LOCALLY FINITE GRAPHS
Shao, Mengqiu
Yang, Yunyan
Zhao, Liang
PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 2025, 153 (02) : 693 - 708
[23] THE CONNECTIVITIES OF LOCALLY FINITE PRIMITIVE GRAPHS
JUNG, HA
WATKINS, ME
COMBINATORICA, 1989, 9 (03) : 261 - 267
[24] DECOMPOSING ENDS OF LOCALLY FINITE GRAPHS
JUNG, HA
NIEMEYER, P
MATHEMATISCHE NACHRICHTEN, 1995, 174 : 185 - 202
[25] Calculus of variations on locally finite graphs
Yong Lin
Yunyan Yang
Revista Matemática Complutense, 2022, 35 : 791 - 813
[26] AUTOMORPHISMS OF INFINITE, LOCALLY FINITE GRAPHS
HALIN, R
NOTICES OF THE AMERICAN MATHEMATICAL SOCIETY, 1972, 19 (01): : A32 - &
[27] Transitive, Locally Finite Median Graphs with Finite Blocks
Wilfried Imrich
Sandi Klavžar
Graphs and Combinatorics, 2009, 25 : 81 - 90
[28] Transitive, Locally Finite Median Graphs with Finite Blocks
Imrich, Wilfried
Klavzar, Sandi
GRAPHS AND COMBINATORICS, 2009, 25 (01) : 81 - 90
[29] Categoricity Spectra of Computable Structures
Bazhenov N.A.
Journal of Mathematical Sciences, 2021, 256 (1) : 34 - 50
[30] Categoricity Spectra for Rigid Structures
Fokina, Ekaterina
Frolov, Andrey
Kalimullin, Iskander
NOTRE DAME JOURNAL OF FORMAL LOGIC, 2016, 57 (01) : 45 - 57

← 1 2 3 4 5 →