most recent 30 from http://mathoverflow.net 2013-05-22T18:44:54Z http://mathoverflow.net/feeds/question/108824 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/108824/a-graph-parameter-possibly-related-to-treewidth Ashley Montanaro 2012-10-04T14:44:14Z 2012-10-05T23:45:04Z

<p>(<a href="http://cstheory.stackexchange.com/questions/12744/a-graph-parameter-possibly-related-to-treewidth" rel="nofollow">Cross-posted</a> from the Theoretical Computer Science StackExchange site after there was no conclusive answer after a week.)</p> <p>I am interested in graphs on $n$ vertices which can be produced via the following process.</p> <ol> <li>Start with an arbitrary graph $G$ on $k\le n$ vertices. Label all the vertices in $G$ as <i>unused</i>.</li> <li>Produce a new graph $G'$ by adding a new vertex $v$, which is connected to one or more <i>unused</i> vertices in $G$, and is not connected to any <i>used</i> vertices in $G$. Label $v$ as <i>unused</i>.</li> <li>Label one of the vertices in $G'$ to which $v$ is connected as <i>used</i>.</li> <li>Set $G$ to $G'$ and repeat from step 2 until $G$ contains $n$ vertices.</li> </ol> <p>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.</p> <p>I would like to know if this process has been studied before. In particular, for arbitrary $k$, <b>is it NP-complete to determine whether a graph has complexity $k$?</b></p> <p>This problem appears somewhat similar to the question of whether $G$ is a <a href="http://cstheory.stackexchange.com/questions/1532/what-is-the-correct-definition-of-k-tree" rel="nofollow">partial $k$-tree</a>, i.e. has <a href="http://en.wikipedia.org/wiki/Treewidth" rel="nofollow">treewidth</a> $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.</p>

http://mathoverflow.net/questions/108824/a-graph-parameter-possibly-related-to-treewidth/108879#108879 Joseph O'Rourke 2012-10-05T01:55:37Z 2012-10-05T23:45:04Z

<p>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$: <br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img src="http://cs.smith.edu/~orourke/MathOverflow/GrowGraphs20.jpg" alt="Growing Graphs" /> <br /> The vertices are numbered in the order in which they were added. <hr /> Here is just one more, this time grown from $K_5$, to give a gestalt view of the influence of the start $G$: <br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img src="http://cs.smith.edu/~orourke/MathOverflow/GraphGrowK5.jpg" alt="Growing from K5" /> <br /></p>