RUS  ENG
Full version
JOURNALS // Sibirskii Matematicheskii Zhurnal // Archive

Sibirsk. Mat. Zh., 2023 Volume 64, Number 1, Pages 98–112 (Mi smj7749)

On universal positive graphs

B. S. Kalmurzaevab, N. A. Bazhenovc, D. B. Alisha

a Al-Farabi Kazakh National University
b Kazakh-British Technical University
c Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk

Abstract: We study the existence of the universal computable numberings and the universal graphs for various classes of positive graphs. It is known that each $\forall$-axiomatizable class of graphs $K$ can be characterized as follows: A graph $G$ belongs to $K$ if and only if for a given family of finite graphs $\mathbf{F}$ no graph in $\mathbf{F}$ is isomorphically embeddable into $G$. If all graphs in $\mathbf{F}$ are weakly connected; then, under additional effectiveness conditions, the corresponding class $K$ has some universal computable numbering and universal positive graph. The effectiveness conditions hold for forests, bipartite graphs, planar graphs, and $n$-colorable graphs (for a fixed number $n$). If $\mathbf{F}$ is a finite family of the graphs with weakly connected complement then the corresponding class $K$ contains a universal positive graph (in general, a universal computable numbering for $K$ may fail to exist).

Keywords: computable reducibility, computable numbering, computably enumerable relation, positive graph.

UDC: 510.53

Received: 06.04.2022
Revised: 07.07.2022
Accepted: 15.08.2022

DOI: 10.33048/smzh.2023.64.110


 English version:
Siberian Mathematical Journal, 2023, 64:1, 83–93

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024