On a certain complexity estimate in graph theory (Q1358054)
From MaRDI portal
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