|
24
1
|
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? (This problem arose in the context of circuit design, where edges in $G$ correspond to wires in a chip layout.) |
|||||
|
|
28
|
See Chung and Graham, On Universal Graphs for Spanning Trees. They prove that the number of edges is $\Theta(n\log n)$. |
|||
|
|
15
|
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. 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 http://arxiv.org/abs/1007.2326), and add some large degree vertices to get all other trees from this. |
|||
|
|
6
|
The standard term is "universal graphs", I think. See http://en.wikipedia.org/wiki/Universal_graph According to that entry the answer is indeed $O(n \log n)$. |
||||||
|
|
0
|
see representation number of graph by ring it is useful. |
||
|
|
