Deprecated: $wgMWOAuthSharedUserIDs=false is deprecated, set $wgMWOAuthSharedUserIDs=true, $wgMWOAuthSharedUserSource='local' instead [Called from MediaWiki\HookContainer\HookContainer::run in /var/www/html/w/includes/HookContainer/HookContainer.php at line 135] in /var/www/html/w/includes/Debug/MWDebug.php on line 372
On a certain complexity estimate in graph theory - MaRDI portal

On a certain complexity estimate in graph theory (Q1358054)

From MaRDI portal





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
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references