10
$\begingroup$

(Cross-posted from the Theoretical Computer Science StackExchange site after there was no conclusive answer after a week.)

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.

$\endgroup$
4
  • 1
    $\begingroup$ Have you worked out the case $k=2$? $\endgroup$ Oct 4 '12 at 16:19
  • 1
    $\begingroup$ This reminds me of the property of k-degeneracy, or "colouring number". Consider the process of reducing a graph to the empty graph by repeatedly removing a vertex of minimum degree; keep track of the maximum of these minimum degrees as you go and call the graph "k-degenerate" if this maximum value is k. $\endgroup$ Oct 5 '12 at 5:51
  • 2
    $\begingroup$ I think the case $k=2$ is equivalent to the following (possibly not useful) "zig-zag ladder" characterisation: can the graph be formed by taking a graph with a bipartite planar embedding (ie. the graph can be drawn in the plane as two columns of vertices, such that all edges are between "left" vertices and "right" vertices), then connecting all "left" vertices with a path from top to bottom, and all "right" vertices with a path from top to bottom. I haven't worked out if recognising graphs of this form is hard, but I suspect it is in P. $\endgroup$ Oct 5 '12 at 9:01
  • $\begingroup$ And thanks for the comment about degeneracy -- it does seem like a similar concept, I should try to think whether it's related. $\endgroup$ Oct 5 '12 at 9:10
4
$\begingroup$

Following Felix's suggestion, and corroborating Ashley's characterization, here are five examples of graphs grown from $K_2$, i.e., $E=\lbrace (1,2) \rbrace$:
      Growing Graphs
The vertices are numbered in the order in which they were added.


Here is just one more, this time grown from $K_5$, to give a gestalt view of the influence of the start $G$:
      Growing from K5

$\endgroup$
3
  • 2
    $\begingroup$ I thought this was how it worked at first, too, but this is wrong. Read 3 more carefully: "Label one of the vertices in $G'$ to which $v$ is connected as used." You can connect 3 to 1 and 2, label 1 used, and then connect 4 to 3 and 2, label 3 used, connect 5 to 4 and 2, and so on. In other words, vertices can have arbitrary high degree for $k$ = 2. $\endgroup$ Oct 5 '12 at 2:00
  • $\begingroup$ @Sam: Thanks, you were correct. I replaced my examples, now following the growth rules (I hope!) more carefully. $\endgroup$ Oct 5 '12 at 11:06
  • $\begingroup$ Thanks for those great pictures, which do follow the rules (unless I've made a mistake myself!). $\endgroup$ Oct 5 '12 at 13:58

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.