Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9514520 | Electronic Notes in Discrete Mathematics | 2005 | 7 Pages |
Abstract
We prove that the split decomposition of a graph is definable by Monadic Second-Order formulas. We also prove that the set of graphs having the same cycle matroid as a given graph is definable from this graph by Monadic Second-Order formulas. These results are consequences of general results on the logical definability of graph decompositions of various types.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Bruno Courcelle,