0
$\begingroup$

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.

  1. For $k>1$ do these classes of graphs have common names?
  2. 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.

$\endgroup$
1
  • $\begingroup$ Thanks for the reference! If you post it as an answer, I'll accept it $\endgroup$
    – Julian
    Oct 19, 2017 at 6:52

1 Answer 1

1
$\begingroup$

These are called $k$-degenerate graphs in the graph theory literature.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.