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 :
بازگشت