The monadic second-order logic of graphs XVI : Canonical graph decompositions
The monadic second-order logic of graphs XVI : Canonical graph decompositions
复制标题
图的一元二阶逻辑 XVI：规范图分解
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
B. Courcelle
中科院分区：
文献类型：
--
作者：
B. Courcelle
本文确立了 Cunnigham 引入的图的分裂分解可以在一元二阶逻辑中定义。这个结果实际上是一个更一般结果的实例，涵盖了规范图分解，例如 2 连通图到 3 连通分量的模分解和 Tutte 分解。作为一个应用，我们证明了与给定的 2-连通图具有相同循环拟阵的图集可以通过 Monadic 二阶公式从该图中定义。
This article establishes that the split decomposition of graphs introduced by Cunnigham, is definable in Monadic Second-Order Logic.This result is actually an instance of a more general result covering canonical graph decompositions like the modular decom- position and the Tutte decomposition of 2-connected graphs into 3-connected components. As an application, we prove that the set of graphs having the same cycle matroid as a given 2-connected graph can be defined from this graph by Monadic Second-Order formulas.