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 条

[1] On Categoricity Spectra for Locally Finite Graphs
Bazhenov N.A.
Marchuk M.I.
Siberian Mathematical Journal, 2021, 62 (5) : 796 - 804
[2] Computable categoricity of graphs with finite components
Csima, Barbara F.
Khoussainov, Bakhadyr
Liu, Jiamou
LOGIC AND THEORY OF ALGORITHMS, 2008, 5028 : 139 - +
[3] CATEGORICITY AND TOPOLOGICAL GRAPHS
Bankston, Paul
HOUSTON JOURNAL OF MATHEMATICS, 2012, 38 (01): : 295 - 310
[4] Flows of locally finite graphs
Hattab H.
Bollettino dell'Unione Matematica Italiana, 2017, 10 (4) : 671 - 679
[5] Locally finite homogeneous graphs
Shawn Hedman
Wai Yan Pong
Combinatorica, 2010, 30 : 419 - 434
[6] THE FACTORIZATION OF LOCALLY FINITE GRAPHS
TUTTE, WT
CANADIAN JOURNAL OF MATHEMATICS-JOURNAL CANADIEN DE MATHEMATIQUES, 1950, 2 (01): : 44 - 49
[7] Homeomorphisms of Locally Finite Graphs
Hawete Hattab
Ezzeddine Salhi
Qualitative Theory of Dynamical Systems, 2016, 15 : 481 - 490
[8] LOCALLY FINITE HOMOGENEOUS GRAPHS
Hedman, Shawn
Pong, Wai Yan
COMBINATORICA, 2010, 30 (04) : 419 - 434
[9] Homeomorphisms of Locally Finite Graphs
Hattab, Hawete
Salhi, Ezzeddine
QUALITATIVE THEORY OF DYNAMICAL SYSTEMS, 2016, 15 (02) : 481 - 490
[10] A DECOMPOSITION OF LOCALLY FINITE GRAPHS
OPOROWSKI, B
DISCRETE MATHEMATICS, 1993, 117 (1-3) : 161 - 168

← 1 2 3 4 5 →