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 条

[41] An index theory for uniformly locally finite graphs
von Below, Joachim
LINEAR ALGEBRA AND ITS APPLICATIONS, 2009, 431 (1-2) : 1 - 19
[42] On the Weiss conjecture for finite locally primitive graphs
Conder, MD
Li, CH
Praeger, CE
PROCEEDINGS OF THE EDINBURGH MATHEMATICAL SOCIETY, 2000, 43 : 129 - 138
[43] Enumerating planar locally finite cayley graphs
Renault, D
GEOMETRIAE DEDICATA, 2005, 112 (01) : 25 - 49
[44] ON K-GRACEFUL, LOCALLY FINITE GRAPHS
SLATER, PJ
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1983, 35 (03) : 319 - 322
[45] Non-reconstructible locally finite graphs
Bowler, Nathan
Erde, Joshua
Heinig, Peter
Lehner, Florian
Pitz, Max
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2018, 133 : 122 - 152
[46] Model geometries dominated by locally finite graphs
Margolis, Alex
ADVANCES IN MATHEMATICS, 2024, 451
[47] Enumerating Planar Locally Finite Cayley Graphs
David Renault
Geometriae Dedicata, 2005, 112 : 25 - 49
[48] ELLIPTIC PROBLEMS ON WEIGHTED LOCALLY FINITE GRAPHS
Imbesi, Maurizio
Bisci, Giovanni Molica
Repovs, Dusan D.
TOPOLOGICAL METHODS IN NONLINEAR ANALYSIS, 2023, 61 (01) : 501 - 526
[49] A sufficient condition for Hamiltonicity in locally finite graphs
Heuer, Karl
EUROPEAN JOURNAL OF COMBINATORICS, 2015, 45 : 97 - 114
[50] Orthogonality and minimality in the homology of locally finite graphs
Diestel, Reinhard
Pott, Julian
ELECTRONIC JOURNAL OF COMBINATORICS, 2014, 21 (03):

← 1 2 3 4 5 →