The monadic second-order logic of graphs. XI: Hierarchical decompositions of connected graphs (Q1960417)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1387344
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | The monadic second-order logic of graphs. XI: Hierarchical decompositions of connected graphs |
scientific article; zbMATH DE number 1387344 |
Statements
The monadic second-order logic of graphs. XI: Hierarchical decompositions of connected graphs (English)
0 references
12 January 2000
0 references
[For the previous parts see Zbl 0877.68087, Zbl 0872.03026, and the citations given there.] This is the eleventh paper in the author's extensive study of the expressive power of monadic second-order (MSO) logic in the realm of graph theory. Here he proves that the unique decompositions of connected graphs introduced by W. Tutte are definable by MSO-formulas. For obtaining this result it is first shown that every 2-dag has a unique canonical decomposition which is MSO-definable; a 2-dag is a (finite) directed acyclic graph in which every vertex lies on a path from a fixed source vertex to a fixed target vertex.
0 references
3-connected graph
0 references
block
0 references
tree
0 references
expressive power of monadic second-order logic
0 references
graph theory
0 references
unique decompositions of connected graphs
0 references
directed acyclic graph
0 references
0 references
0 references
0 references
0.8478295803070068
0 references
0.8153823018074036
0 references
0.7905721068382263
0 references
0.7880445122718811
0 references
