A graph parameter possibly related to treewidth - MathOverflow 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 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 Answer by Joseph O'Rourke for A graph parameter possibly related to treewidth 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>