(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.