A graph parameter possibly related to treewidth 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.

4th October 2012: Question cross-posted to MathOverflow after there was no conclusive answer after a week (though thanks for the info about causal flows).
Though we've chatted about this in person before, I'll add this in the hope that this will allow someone else to provide a complete answer.
In your process of adding vertices, define a partial function $f:V(G) \rightharpoonup V(G)$ from each vertex $v$ which gets used, to the vertex which was added when $v$ got used. Then it turns out that $f$ is a (causal) flow function (p. 39), which is a restricted version of a path cover. Indeed, your description of these graphs of &quot;complexity k&quot; (given a set of vertices which are to be the initially unused vertices, and the final unused vertices) is precisely the star decomposition of a &quot;geometry&quot; with a causal flow (p. 46 of the above article).
Although these &quot;causal flows&quot; have been studied mainly in the context of (measurement-based) quantum computation — where they are motivated by certain structures of unitary circuits — there are graph-theoretic results about them which are totally divorced from quantum computation:

Uniqueness modulo endpoints: the graphs with &quot; complexity $k$ &quot; are precisely those for which there exist (possibly intersecting) sets $S,T \subseteq V(G)$, both of size $k$, such that $G$ has exactly one path cover of size $k$ whose paths start in $S$ and end in $T$.
Extremal graphs: A graph on $n$ vertices which has &quot;complexity $k$&quot; has at most $kn - \binom{k+1}{2}$ edges.

Using these results, and given a candidate pair of sets $S,T$, determining whether or not they &quot;subtend&quot; a unique path cover in this way can be determined in time $O(k^2 n)$; but finding whether or not such sets of endpoints exist that is the apparent difficulty, and the extremal result above (which is only a necessary condition) seems to represent the state of the art in efficient criteria to determine whether such sets exist.