most recent 30 from http://mathoverflow.net 2013-06-20T09:39:26Z http://mathoverflow.net/feeds/question/54193 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/54193/graph-containing-all-trees Bill Bradley 2011-02-03T13:16:08Z 2011-02-07T14:07:29Z

<p>Consider graphs on $n$ nodes. I am trying to find a graph $G$ that contains all $n$-node trees as sub-graphs but contains as few edges as possible. The complete graph $K_n$ suffices, but can we get by with fewer edges? Maybe $O(n)$ edges?</p> <p>(This problem arose in the context of circuit design, where edges in $G$ correspond to wires in a chip layout.)</p>

http://mathoverflow.net/questions/54193/graph-containing-all-trees/54196#54196 Flo Pfender 2011-02-03T13:37:36Z 2011-02-03T13:37:36Z

<p>Well, $O(n)$ will not do, as you need 1 vertex of degree $n-1$, a total of two vertices of degree $\ge \frac{n}{2}$, etc., to embedd all the trees with few vertices of high degree and only leaves otherwise. That should get you $cn\log n$ edges as a lower bound. </p> <p>My guess is that this should be about right asymptotically, as you should be able to take a random graph with average degree $c\Delta\log n$ to get (all?) trees of max degree $\Delta$ (see <a href="http://arxiv.org/abs/1007.2326" rel="nofollow">http://arxiv.org/abs/1007.2326</a>), and add some large degree vertices to get all other trees from this.</p>

http://mathoverflow.net/questions/54193/graph-containing-all-trees/54199#54199 Manor Mendel 2011-02-03T14:41:53Z 2011-02-03T14:41:53Z

<p>The standard term is "universal graphs", I think. See <a href="http://en.wikipedia.org/wiki/Universal_graph" rel="nofollow">http://en.wikipedia.org/wiki/Universal_graph</a> According to that entry the answer is indeed $O(n \log n)$.</p>

http://mathoverflow.net/questions/54193/graph-containing-all-trees/54211#54211 David Eppstein 2011-02-03T16:40:08Z 2011-02-03T16:40:08Z

<p>See Chung and Graham, <a href="http://www.math.ucsd.edu/~ronspubs/83_06_universal_trees.pdf" rel="nofollow">On Universal Graphs for Spanning Trees</a>. They prove that the number of edges is $\Theta(n\log n)$.</p>

http://mathoverflow.net/questions/54193/graph-containing-all-trees/54636#54636 Mohsen 2011-02-07T14:07:29Z 2011-02-07T14:07:29Z

<p>see <a href="http://www.units.muohio.edu/sumsri/sumj/2008/Bernsteinpaper.pdf" rel="nofollow">representation number of graph by ring</a></p> <p>it is useful.</p>