On a certain complexity estimate in graph theory (Q1358054)
From MaRDI portal
| This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: On a certain complexity estimate in graph theory |
scientific article; zbMATH DE number 1023956
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On a certain complexity estimate in graph theory |
scientific article; zbMATH DE number 1023956 |
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