Completeness spanning trees

Question

A spanning tree of a graph is called a completeness tree if the set of its leaves induces a complete subgraph in the host graph. Given a graph $G$ and an integer $k$, what is the complexity of deciding if $G$ contains a completeness tree with at most $k$ leaves?

A reason for asking this question is that the corresponding problem for independency trees is NP-complete, here an independency tree is a spanning tree such that the set of its leaves is an independent set in the host graph.

Another reason is this question (and the corresponding answers). It turns out that every spanning tree of $G$ is a completeness tree if and only if $G$ is a complete graph or a cycle.

Answer 1

In a triangle-free graph, a completeness tree must be a Hamiltonian cycle (minus one of its edges). ISGCI says Hamiltonian cycle is NP-complete in triangle-free graphs. Therefore, so is finding a completeness tree (regardless of any restriction on max number of leaves).

Answer 2

I cannot beat David in the elegance of his answer. But after spending al lot of time on thinking about this problem I would like to betray my solution to you though ;)

Let $k \ge 2$ be a fixed interger. Given $G$, construct $H$ as follows:Take two copies $G_1$, $G_2$ and a clique $Q$ on $k$ vertices $x, x_1, x_2, \ldots, x_{k-1}$, a new vertex $y$, fix a vertex $v_1 \in G_1$ and a vertex $v_2 \in G_2$. $H$ is obtained from $G_1, G_2, Q$ and $y$ by joining $x$ to $v_1$, joining $x_1, x_2, \ldots, x_{k-1}$ to $v_2$ and joining all neighbors of $v_1$ in $G_1$ and all neighbor of $v_2$ in $G_2$ to $y$.

Then it can be easily seen that $G$ has a Hamiltonian cycle if and only if $H$ has a completeness tree with at most $k$ leaves.