Title of article
Graph decompositions definable in monadic second-order logic
Author/Authors
Courcelle، نويسنده , , Bruno، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2005
Pages
7
From page
13
To page
19
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.
Keywords
Matroid , Monadic second-order logic , Graph decomposition , split decomposition
Journal title
Electronic Notes in Discrete Mathematics
Serial Year
2005
Journal title
Electronic Notes in Discrete Mathematics
Record number
1454075
Link To Document