| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 435373 | Theoretical Computer Science | 2016 | 10 Pages |
Abstract
In this paper, we consider the problem of finding a spanning tree in a graph that maximizes the number of leaves. We show the NPNP-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 APXAPX-hard on 5-regular graphs. Finally, we extend our proof to k -regular graphs for odd k>5k>5.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Alexander Reich,