Degree-preserving spanning trees in small-degree graphs (Q1579547)

The degree-preserving spanning tree problem is to find, in a given connected graph \(G= (V,E)\), a spanning tree \(T= (V,F)\) with maximum number of vertices of the kind that all edges of \(E\) incident with such vertices belong to \(F\). The corresponding decision problem is denoted by DPST. The paper shows that the DPST problem is NP-complete for (1) bipartite planar graphs in which each vertex has degree at most 5; (2) planar graphs in which each vertex has degree at most 4; and (3) planar graphs in which each vertex has degree at most 3. Moreover, the paper establishes relations of the DPST problem to the Steiner problem in graphs and the feedback vertex set problem.