Complexity of the maximum leaf spanning tree problem on planar and regular graphs

摘要

In this paper, we consider the problem of finding a spanning tree in a graph that maximizes the number of leaves. We show the NP-hardness of this problem for graphs that are planar and cubic. Our proof will be an adaption of the proof for arbitrary cubic graphs in Lemke (1988) [9]. Furthermore, it is shown that the problem is APX-hard on 5-regular graphs. Finally, we extend our proof to k-regular graphs for odd k > 5. (C) 2016 Elsevier B.V. All rights reserved.