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).
A graph parameter possibly related to treewidth
ds.algorithms;graph theory;treewidth