Fully decomposable split graphs
Fully decomposable split graphs
复制标题
DOI：
10.1016/j.ejc.2011.09.044
复制
发表时间：
2009-11
期刊：
影响因子：
--
通讯作者：
H. Broersma;D. Kratsch;G. Woeginger
中科院分区：
文献类型：
--
作者：
H. Broersma;D. Kratsch;G. Woeginger
我们讨论有关将分裂图划分为连通部分的各种问题。我们的主要结果是一个多项式时间算法，它决定了一个给定的分裂图是否是完全可分解的，也就是说，它是否可以被划分成阶为α1，α 2，...，α k的连通部分，对于每个α1，α2，...，α k和图的阶。与此相反，我们证明了对于给定的图的阶的划分α1，α2，.，α k，一个给定的分裂图是否可以划分为阶为α1，α2，.，α k的连通部分的判定问题是NP-难的.
We discuss various questions around partitioning a split graph into connected parts. Our main result is a polynomial time algorithm that decides whether a given split graph is fully decomposable, that is, whether it can be partitioned into connected parts of orders α1,α2,…,αkfor every α1,α2,…,αksumming up to the order of the graph. In contrast, we show that the decision problem whether a given split graph can be partitioned into connected parts of orders α1,α2,…,αkfor a given partition α1,α2,…,αkof the order of the graph, is NP-hard.