On the SPANNING \(k\)-TREE problem (Q686254): Difference between revisions

A \(k\)-tree \(T\) is defined recursively as being either a clique of size \(k\) or having a vertex \(x\) whose neighbourhood is a clique of size \(k\) and such that \(T-x\) is a \(k\)-tree. (Note that \(k\)-trees are not trees, if \(k>1\).) The following SPANNING \(k\)-TREE problem is known to be NP-complete: given a graph \(G\), does \(G\) possess a subgraph which is a \(k\)-tree and contains every vertex of \(G\)? The main result of the paper: the SPANNING \(k\)-TREE problem remains NP-complete for all \(k \geq 2\) even when restricted to any of the following classes of graphs: split graphs, graphs with maximum degree at most \(3k+2\), planar graphs (for \(k=2)\).