A graph parameter possibly related to treewidth

Question

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

1. Start with an arbitrary graph $G$ on $k\le n$ vertices. Label all the vertices in $G$ as unused.
2. 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.
3. Label one of the vertices in $G'$ to which $v$ is connected as used.
4. 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).

Answer 1

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 "complexity k" (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 "geometry" with a causal flow (p. 46 of the above article).

Although these "causal flows" 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 " complexity $k$ " 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 "complexity $k$" 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 "subtend" 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.

Answer 2

All graphs of complexity $k$ has path-width at most $k$. At every step the set of unused nodes is a separator separating the used nodes from those already created. So at every step, when you add a vertex, you can create a bag containing that vertex plus all unused vertices and connect the bag at the end of the path decomposition. This will be a valid path decomposition.

Because of the "which $v$ is connected" in point 3 and 2 the path-width can be much smaller than $k$. I am not sure about deciding if $G$ is a complexity $k$, but as Niel says, there must be a path cover of size k, but not only a path cover, the paths have to be induced. And inbetween the paths we can have this zig-zag pattern. We can in $f(k) \cdot poly(n)$ time compute an optimal path decomposition, then we can use this decomposition to do dynamic programming while keeping track of the different segments of these $k$ paths, which path they belong to and the order of segments belonging to the same path. And for each pair of segments belonging to different paths we only need to know the first and last path of the zig-zag.

Therefore I think we can decide if a graph has complexity $k$ in $f(k) \cdot poly(n)$ time.