Definition. For $k\ge 1$ we call a graph $k$-constructible if it can be obtained from the empty graph by subsequently adding new vertices and connecting them to at most $k$ previously existing vertices.
First two elementary observation:
- A graph is $k$-constructible if and only if it is $k$-destructible in the sense that it can be transformed into the empty graph by subsequently removing vertices of degree at most $k$ and its adjacent edges.
- A graph is $k$-destructible if and only if it is so greedily. By this I mean that one can subsequently remove any vertex of degree at most $k$ to obtain the empty graph.
- A graph is $1$-constructible if and only if it is a forest. In other words, a graph is $1$-constructible if it contains no cycles, i.e., if it does not contain $K_3$ as a minor.
Questions.
- For $k>1$ do these classes of graphs have common names?
- Is there an alternative more directly verifiable condition to figure out whether a graph is $k$-constructible?
I would also be very happy to know answers to these questions for $k=2$ only.
It is obvious that a graph containing $K_4$ as a subgraph cannot be $2$-constructible. So I briefly thought whether graphs might be $2$-constructible if and only if they do not contain $K_4$ as a minor. But this turns out to be wrong since a $K_4$ with one edge subdivided into two edges is $2$-constructible.
