Fully decomposable split graphs
Copyright policy )Fully decomposable split graphs
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 a1,a2,…,ak for every a1,a2,…,ak summing 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 a1,a2,…,ak for a given partition a1,a2,…,ak of the order of the graph, is NP-hard.
- Technical University Eindhoven Netherlands
- Metz Germany
- Durham University United Kingdom
- University of Twente Netherlands
- Eindhoven University of Technology Netherlands
EWI-22740, Graph decomposition - integer partition - computational complexity, Fully decomposable, Graph decomposition, METIS-266492, IR-71247, Theoretical Computer Science, Computational complexity, EWI-17838, Arbitrarily vertex decomposable, Computational Theory and Mathematics, Integer partition, Split graph, Geometry and Topology, MSC-05C, METIS-296435, IR-83468, Partitioning
EWI-22740, Graph decomposition - integer partition - computational complexity, Fully decomposable, Graph decomposition, METIS-266492, IR-71247, Theoretical Computer Science, Computational complexity, EWI-17838, Arbitrarily vertex decomposable, Computational Theory and Mathematics, Integer partition, Split graph, Geometry and Topology, MSC-05C, METIS-296435, IR-83468, Partitioning
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).5 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!