More aspects of arbitrarily partitionable graphs (Q2158201): Difference between revisions

An \(n\)-vertex graph \(G\) is arbitrarily partitionable (AP) if for every sequence of numbers \(n_1,\dots, n_p\) which sum up to \(n\), there is a vertex partition \(V_1,\dots, V_p\) of \(V(G)\), where \(|V_i| = n_i\) and \(G[V_i]\) induces a connected graph for all \(1 \leq i \leq p\). If this partition can be done for a single sequence \(\pi = (n_1,\dots, n_p)\), we say \(\pi\) is realizable in \(G\). The authors study these concepts in two different ways. 1) Computational aspects. The authors consider two decision problems, REALIZATION (given a graph \(G\), and a sequence \(\pi\), is \(\pi\) realizable in \(G\)?) and AP (given a graph \(G\), it is AP?). In the negative side, it is shown that REALIZATION is NP-complete even if restricted to disconnected graphs, subdivided stars, series-parallel graphs, or \(k\)-connected graphs, for a given \(k\). On the positive side, it is shown that certain families of graphs admit polynomial kernels for the AP problem (i.e. a polynomial set of sequences pi such that \(G\) in a given class is AP if and only if every sequence in the set is realizable). 2) Since every graph with a Hamiltonian path is easily seen to be AP, the authors investigate conditions that ensure the graph has a Hamiltonian path and try to weaken those conditions to see if they still can be used to ensure AP instead. They show that weakenings of Fleischner's condition (which says that squares of 2-connected graphs are Hamiltonian) in general do not suffice to ensure AP; something similar is shown for the class of net-claw-free graphs (which are known to be Hamiltonian).