|
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.
Received: 06.04.2022 Revised: 07.07.2022 Accepted: 15.08.2022
Citation:
B. S. Kalmurzaev, N. A. Bazhenov, D. B. Alish, “On universal positive graphs”, Sibirsk. Mat. Zh., 64:1 (2023), 98–112; Siberian Math. J., 64:1 (2023), 83–93
Linking options:
https://www.mathnet.ru/eng/smj7749 https://www.mathnet.ru/eng/smj/v64/i1/p98
|
Statistics & downloads: |
Abstract page: | 74 | Full-text PDF : | 15 | References: | 25 | First page: | 4 |
|