(Cross-posted from the Theoretical Computer Science StackExchange site after there was no conclusive answer after a week.)

I am interested in graphs on $n$ vertices which can be produced via the following process.

- Start with an arbitrary graph $G$ on $k\le n$ vertices. Label all the vertices in $G$ as
*unused*. - Produce a new graph $G'$ by adding a new vertex $v$, which is connected to one or more
*unused*vertices in $G$, and is not connected to any*used*vertices in $G$. Label $v$ as*unused*. - Label one of the vertices in $G'$ to which $v$ is connected as
*used*. - Set $G$ to $G'$ and repeat from step 2 until $G$ contains $n$ vertices.

Call such graphs "graphs of complexity $k$" (apologies for the vague terminology). For example, if $G$ is a graph of complexity 1, $G$ is a path.

I would like to know if this process has been studied before. In particular, for arbitrary $k$, **is it NP-complete to determine whether a graph has complexity $k$?**

This problem appears somewhat similar to the question of whether $G$ is a partial $k$-tree, i.e. has treewidth $k$. It is known that determining whether $G$ has treewidth $k$ is NP-complete. However, some graphs (stars, for example) may have much smaller treewidth than the measure of complexity discussed here.