On a certain complexity estimate in graph theory (Q1358054): Difference between revisions
From MaRDI portal
Removed claim: author (P16): Item:Q1717396 |
ReferenceBot (talk | contribs) Changed an Item |
||
| (2 intermediate revisions by 2 users not shown) | |||
| Property / author | |||
| Property / author: Sergeĭ Vladimirovich Sudoplatov / rank | |||
Normal rank | |||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Superstable graphs / rank | |||
Normal rank | |||
Latest revision as of 17:00, 27 May 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On a certain complexity estimate in graph theory |
scientific article |
Statements
On a certain complexity estimate in graph theory (English)
0 references
14 August 1997
0 references
A first-order theory \(T\) is said to be an \(n\)-theory if each formula is equivalent in \(T\) to a Boolean combination of formulas with at most \(n\) free variables. For a weakly saturated graph \(\Gamma\), the author gives a sufficient condition for its theory to be an \(n\)-theory. Unfortunately, there are some mistakes in the translation, for example, a correcter translation of the title is ``On a certain complexity estimate of theories of graphs'' and the term ``cutpoint'' should be used instead of the term ``junction point''.
0 references
first-order theory
0 references
\(n\)-theory
0 references
weakly saturated graph
0 references
connected component
0 references
block
0 references
cycle
0 references
weakly saturated model
0 references
cutpoint
0 references
