On Halin subgraphs and supergraphs Original Research Article

In this paper, we present two complexity results. The first pertains to the problem of finding Halin subgraphs while the second is a supergraph version which asks if a given graph is a subgraph of any Halin graph. Both of these problems are shown to be hard which, in turn, provides somewhat damaging evidence relative to the veracity of heuristic approaches employing Halin graphs as approximations.