Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

(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.

share|improve this question
1  
Have you worked out the case $k=2$? –  Felix Goldberg Oct 4 '12 at 16:19
1  
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. –  Gordon Royle Oct 5 '12 at 5:51
2  
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. –  Ashley Montanaro Oct 5 '12 at 9:01
    
And thanks for the comment about degeneracy -- it does seem like a similar concept, I should try to think whether it's related. –  Ashley Montanaro Oct 5 '12 at 9:10
add comment

1 Answer 1

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

share|improve this answer
2  
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. –  Sam Hopkins Oct 5 '12 at 2:00
    
@Sam: Thanks, you were correct. I replaced my examples, now following the growth rules (I hope!) more carefully. –  Joseph O'Rourke Oct 5 '12 at 11:06
    
Thanks for those great pictures, which do follow the rules (unless I've made a mistake myself!). –  Ashley Montanaro Oct 5 '12 at 13:58
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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